拼多多2021-04-09春招筆試 服務端開發 解題報告 Apare_xzc

拼多多2021-04-09春招筆試 服務端開發 解題報告 Apare_xzc

2021-04-09 15:00-17:00

2小時4道編程題
100% 100% 46.7% 100%
第三題有兩個case沒寫完

題目描述見代碼注釋

第一題：尖峰陣列

差不多叫這個名字，
求一個先遞增在遞減的最大連續子陣列的長度，簡單DP

//拼多多2021-04-09 15:00 -17:00 
//春招服務端開發筆試題
//時長2小時，編程題4道 * 25分/道 
//
//第一題，給一個長度不超過200的數
//組，求最長的尖峰陣列B的長度len
//B0 < B1 < B2 < Bk > B[k+1] > B[k+2] > B[len-1] 

/*
簡單DP, 從左到右維護左端最大遞增長度L[i]，
從右到左維護右端最大遞減長度R[i]，然后取
ans = max(ans, L[i] + R[i] + 1)即可
L[i] = (i==0   || a[i]<=a[i-1]) ? 0 : L[i-1]+1
R[i] = (i==n-1 || a[i]<=a[i-1]) ? 0 : R[i+1]-1 
*/ 
#include <bits/stdc++.h>
using namespace std;
int a[200];
int L[200], R[200];
int main(void) {
	int n;
	cin>>n;
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	L[0] = 0;
	for (int i = 1; i < n; ++i) {
		if (a[i] > a[i-1]) {
			L[i] = L[i-1] + 1;
		} else {
			L[i] = 0;
		}
	}
	R[n-1] = 0;
	for (int i = n-2; i >=0; --i) {
		if (a[i] > a[i+1]) {
			R[i] = R[i+1] + 1;
		}  else {
			R[i] = 0;
		}
	}
	int ans = 0;
	for (int i = 1; i < n-1; ++i) {
		if (L[i] && R[i]) {
			ans = max(ans, L[i] + R[i] + 1);
		}
	}
	cout << ans << endl;

	return 0;
} 

第二題 快樂數

從小到大暴力check

//第二題，一個數十進制形式如果除了0,1,只有最多一個其他數字N，
//那么就就是快樂數，比如 3, 120, 1777都是快樂數，現在輸入一個
//數字x,求一個最小的y，是x的正整數倍,并且是快樂數，
//input:3
//output:3
//
//input: 235
//output:1410
//資料范圍x<=200 
/*
從小到大暴力嘗試即可， 
*/ 
#include <bits/stdc++.h>
using namespace std;
int main(void) {
	long long x;
	cin >> x;
	for (int i = 1; i < 1000000; ++i) {
		long long y = x * i;
		long long yy = y;
		set<int> st;
		while (y>0) {
			int d = y % 10;
			y /= 10;
			if (d > 1) {
				st.insert(d);
			}
		} 
		if ((int)st.size() < 2) {
			cout<<yy<<endl;
			return 0;
		}
	}
	cout << -1 << endl;
	
	return 0;
} 

第三題：多多的字串II

給一個長度不超過1E6的字串S（只包含小寫字母’a’~‘z’）和正整數k，求長度和S相同，字典序不超過S的，每個字符出現次數都是k的整數倍的字串 之中 字典序最大的那個，
先二分答案求和S相同的位數，然后再貪心，
稍微有些復雜，見代碼，
樣例已經通過，并且自測了k = 2，len(s) = 4的全部資料和k = 2, len(s) = 6的部分資料，
class Solution用于求解， namespace BrouteFource中封裝了暴力求解的函式，

#include <bits/stdc++.h>
using namespace std;

const int M = 1E6+10;

namespace BrouteFource {
    bool HasPreStr(string& s) {
        int len = s.length();
        assert(len > 0);
        bool flag = false;
        for (int i = 0; i < len; ++i) {
            if (s[i] != 'a') {
                flag = true;
                break;
            }
        }
        if (!flag) { // 全a
            return false;
        }
        if (s[len-1] != 'a') {
            s[len-1]--;
            return true;
        } else {
            int index = len-1;
            for (;index >= 0; --index) {
                if (s[index] == 'a') {
                    s[index] = 'z';
                } else {
                    break;
                }
            }
            assert(index >= 0);
            s[index]--;
            return true;
        }
    }
    void PrintBtoS(string s) {
        cout << s << endl;
        while (HasPreStr(s)) {
            cout << s << endl;
        }
    }
    bool check(string s, int k) {
        unordered_map<char,int> mp;
        for (auto x : s) {
            mp[x]++;
        }
        for (auto pr : mp) {
            if (pr.second % k > 0) {
                return false;
            }
        }
        return true;
    }
    string GetAns(string s, int k) {
        int len = s.length();
        if (len % k > 0) {
            return "-1";
        }
        string ans = "-1";
        while (1) {
            if (check(s, k)) {
                ans = s;
                break;
            }
            if (!HasPreStr(s)) {
                break;
            }
        }
        return ans;
    }
}

class Solution {
private:
    static const int N;
    int cnt[300];
    int bucket[300];
    int k, t, len;
    char * s;
    char * p;
    int getRight();
    bool check(int mid);
public:
    Solution();
    ~Solution();
    bool Input();
    string solve();
    int GetK() {
        return this->k;
    }
    string GetString() {
        return string(s);
    }
};
const int Solution::N = 1E6+10;

Solution::Solution() {
    p = new char[N];
    s = new char[N];
}
Solution::~Solution() {
    delete []p;
    delete []s;
}
bool Solution::Input() {
    if (scanf("%d%s", &k, s) == EOF) {
        return false;
    }
    len = strlen(s);
    for (int i = 0; i < len; ++i) {
        assert(islower(s[i]));
    }
    t = len / k;
    return true;
}

bool Solution::check(int mid) {
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= mid; ++i) {
        p[i] = s[i];
        cnt[(int)s[i]]++;
    }
    memset(bucket, 0, sizeof(bucket));
    int curSumT = 0;
    for (int ch = 'a'; ch <= 'z'; ++ch) {
        curSumT += cnt[ch] / k + (cnt[ch] % k != 0);
        if (curSumT > t) {
            return false;
        }
        if (cnt[ch] % k > 0) {
            bucket[ch] += k - cnt[ch] % k;
        }
    }
    if (curSumT < t) {
        bucket['a'] += (t - curSumT) * k;
    }
    int index = mid + 1;
    for (int ch = 'a'; ch <= 'z'; ++ch) {
        while (bucket[ch]--) {
            p[index++] = (char)ch;
        }
    }
    p[len] = 0;
    return strcmp(p, s) <= 0;
}
int Solution::getRight() {
    set<char> st;
    int R = len;
    for (int i = 0; i < len; ++i) {
        st.insert(s[i]);
        if ((int)st.size() > t) {
            i = R;
            break;
        }
    }
    return R;
}
string Solution::solve() {
    if (len % k) {
        return "-1";
    }
    if (k == 1) {
        return string(s);
    }

    int L = -1;
    int R = getRight();
    
    while (R - L > 1) {
        int mid = (R + L) >> 1;
        if (check(mid)) {
            L = mid;
        } else {
            R = mid;
        }
    }
    if (L == len - 1) {
        return string(s);
    }
    if (L == -1) {
        assert(s[0] != 'a');
        memset(bucket, 0, sizeof(bucket));
        bucket[s[0]-1] = k - 1;
        bucket['z'] = (t-1) * k;
        int smallch = (char)(s[0] - 1);
        p[0] = smallch;
        int index = 1;
        while (bucket['z']--) {
            p[index++] = 'z';
        }
        while (bucket[smallch]--) {
            p[index++] = smallch;
        }
        assert(index == len);
        p[len] = 0;
        return string(p);
    }
    memset(bucket, 0, sizeof(bucket));
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i <= L; ++i) {
        p[i] = s[i];
        cnt[s[i]]++;
    }
    int curSumT = 0;
    for (int ch = 'a'; ch <= 'z'; ++ch) {
        curSumT += cnt[ch] / k + (cnt[ch] % k != 0);
        if (cnt[ch] % k > 0) {
            bucket[ch] += k - cnt[ch] % k;
        }
    }
    assert(curSumT <= t);
    int index = L + 1;
    for (;index < len; ++index) {
        assert(s[index] != 'a');
        int smallch = s[index] - 1;
        if (curSumT == t) {
            bool flag = false;
            for (int ch = smallch; ch >= 'a'; --ch) {
                if (bucket[ch] > 0) {
                    --bucket[ch];
                    p[index++] = ch;
                    for (ch = 'z'; ch >= 'a'; --ch) {
                        while (bucket[ch]--) {
                            p[index++] = (char)ch;
                        }
                    }
                    assert(index == len && 1 == 1);
                    p[len] = 0;
                    return string(p);
                }
            }
            assert(flag);
        } else { // curSumT < t
            if (bucket[smallch] > 0) {
                p[index++] = (char)smallch;
                bucket[smallch]--;
                bucket['z'] += max(0, t - curSumT) * k;
                for (int ch = 'z'; ch >= 'a'; --ch) {
                    while (bucket[ch]--) {
                        p[index++] = (char)ch;
                    }
                }
                assert(index == len && 2 == 2);
                p[len] = 0;
                return string(p);
            } else { //bucket[smallch] == 0
                ++curSumT;
                bucket[smallch] = k - 1;
                bucket['z'] += max(0, (t - curSumT)) * k;
                p[index++] = smallch;
                for (int ch = 'z'; ch >= 'a'; --ch) {
                    while (bucket[ch]--) {
                        p[index++] = (char)ch;
                    }
                }
                assert(index == len && 3 == 3);
                p[len] = 0;
                return string(p);
            }
        }
    }
    return "-1";
}


int main(void) {
    freopen("in_k2_len6", "r", stdin);
    freopen("out_k2_len6", "a", stdout);
    Solution * pSol = new Solution();

    while(pSol->Input()) {
        string ans = pSol->solve();
        //std::cout << ans << "\n";
        string bfans = BrouteFource::GetAns(pSol->GetString(), pSol->GetK());
        //Gstd::cout << bfans << "\n";
        assert(ans == bfans);
        cout<<",\n    {'k':"<<pSol->GetK()<<",'s':'"<<pSol->GetString()<<"','ans':'"<<ans<<"'}";
    }

    delete pSol;

    return 0;
}

還寫了個makedata.cpp 用來按照字典序順序生成測驗樣例

#include <bits/stdc++.h>
using namespace std;

bool HasNextStr(string& s) {
    string tmp = s;
    int len = s.length();
    if (len == 0) {
        return false;
    }
    bool flag = false;
    for (int i = 0; i < len; ++i) {
        assert(islower(s[i]));
        if (s[i] < 'z') {
            flag = true;
            break;
        }
    }
    if (!flag) {
        return false;
    }
    int i = len - 1;
    for (; i >= 0; --i) {
        if (s[i] == 'z') {
            s[i] = 'a';
        } else {
            break;
        }
    }
    assert(i>=0 && 1 == 1);
    
    //assert(i >= 0);
    s[i]++;
    return true;
}

int main(void) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    freopen("in_k2_len6", "w", stdout);
    int k = 2;
    string s = "aaaaaa";
    do {
        cout << k << "\n" << s << "\n";
    } while(HasNextStr(s));

    return 0;
}

第四題：多多的數字猜想

求N!的M進制形式末尾有多少個0.

//求N! 的 M進制形式末尾有多少個0
//2 <= N,M <= 1E9

/*
將M分解質因數，M = d1^x1 * d2^x2 * ... dk^xk 
然后求N！內每個質因數的個數pd1, pd2, pd3
然后答案為min(pdi/xi) 
*/ 
#include <bits/stdc++.h>
using namespace std;
int main(void) {
	int n,m;
	cin>>n>>m;
	vector<pair<int,int> > vd;
	int x = m;
	for (int i = 2; i <= x / i; ++i) {
		int cnt = 0;
		while (x % i == 0) {
			++cnt; 
			x /= i;
		}
		if (cnt > 0) {
			vd.push_back(make_pair(i,cnt));
		}
	}
	if (x > 1) {
		vd.push_back(make_pair(x,1));
	}
	
	long long res = 1E13;
	for (auto pr : vd) {
		int d = pr.first;
		int c = pr.second;
		int y = n;
		long long tot = 0;
		while (y > 0) {
			y /= d;
			tot += y;
		}
		res = min(res, tot /  c);
	}
	cout << res << endl;	
	return 0;
} 

筆試過了，Good Luck，

2021.4.14 0:17