本文實例講述了基于C++的拼多多算法在線筆試題。分享給大家供大家參考，具體如下：
最近在狼廠實習中，很久沒做題了。秋招第一發， 拼多多。。。 四個簡單題，看到有些人竟然覺得難？ 我來降一發自己的RP，這題目覺得難的，如果你拿到比我好的Offer，我是不服氣的。。
四個題。。。其實我也就寫了40分鐘吧。。不過最后也沒有滿分， 390/400， 第三題不知道為嘛一直有10分過不了。。
更一下, 剛剛好像發現第三題。。。這個>號， 我寫的是>= ....? 可是我看題目好像是 >= 呀。。。
第一題:
要求時間復雜度O(n)， 空間復雜度O(1)。
那么其實答案有兩種情況，最大的三個數相乘 || 最小的兩個數 * 最大的數。 時間復雜度O(n)，瞬間想到時間復雜度O(n)求k大的經典算法，分治法！
#include <cstdio>#include <iostream>#include <string>#include <algorithm>using namespace std;const int N = 1e6 + 10;long long a[N];int k;int partition(int l,int r) { while(l != r) { while(a[r] >= a[l] && r > l) r--; if(l == r) break; swap(a[r],a[l]); while(a[l] < a[r] && r > l) l++; if(l < r) swap(a[r],a[l]); } return l;}long long solve(int l,int r) { int now = partition(l,r); if(k < now) return solve(l,now-1); else if(k > now) return solve(now+1,r); else return a[now];}int main() { int n; while(~scanf("%d", &n)) { for(int i = 0; i < n; ++i) { scanf("%lld", &a[i]); } k = n - 1; long long x1 = solve(0, n-1); k = n - 2; long long x2 = solve(0, n-2); k = n - 3; long long x3 = solve(0, n-3); long long Ans = x1 * x2 * x3; if(n > 3) { k = 0; long long y1 = solve(0, n-1); k = 1; long long y2 = solve(0, n-2); Ans = max(Ans, y1*y2*x1); } printf("%lld/n", Ans); } return 0;}第二題:
大數相乘，模板題， 找了個模板。。。
#include <iostream>#include <cstring>#include <string>#include <algorithm>using namespace std;const int N = 1e5 + 10;string c1, c2;int a[N], b[N], r[N];void solve(int a[], int b[], int la, int lb) { int i, j; for(i = 0; i != N; i++) r[i] = 0; for(i = 0; i != la; i++) { for(j = 0; j != lb; j++) { int k = i + j; r[k] += a[i] * b[j]; while(r[k] > 9) { r[k + 1] += r[k] / 10; r[k] %= 10; k++; } } } int l = la + lb - 1; while(r[l] == 0 && l > 0) l--; for(int i = l; i >= 0; i--) cout << r[i]; cout << endl;}int main() { while(cin >> c1 >> c2) { int la = c1.size(), lb = c2.size(); for(int i = 0; i != la; i++) a[i] = (int)(c1[la - i - 1] - '0'); for(int i = 0; i != lb; i++) b[i] = (int)(c2[lb - i - 1] - '0'); solve(a, b, la, lb); } return 0;}第三題：
貪心啊， 我是按照 盡量滿足最小人的需求來貪心的。。。一直90%? 有人是用盡量使用掉最大的巧克力來貪的，100%， 來個反例好不好？
#include <cstdio>#include <iostream>#include <string>#include <algorithm>using namespace std;const int N = 3e6 + 10;long long w[N], h[N];int main() { int n, m; while(~scanf("%d", &n)) { for(int i = 0; i < n; ++i) { scanf("%lld", &h[i]); } scanf("%d", &m); for(int i = 0; i < m; ++i) { scanf("%lld", &w[i]); } sort(h, h + n); sort(w, w + m); int Ans = 0; for(int i = 0, j = 0; i < n && j < m; ) { if(w[j] >= h[i]) { ++Ans; ++i, ++j; } else { ++j; } } printf("%d/n", Ans); } return 0;}第四題：
迷宮問題， 有趣的是多了一把鑰匙。。。 一看門不超過10個。。。M, N <=100...想了想狀態數。。。直接狀態壓縮吧。。 之后就是一個非常暴力可恥的狀態壓縮bfs。。。然后就一發AC了。。
#include <cstdio>#include <iostream>#include <string>#include <queue>#include <map>#include <algorithm>using namespace std;const int N = 110;char mz[N][N];bool vis[N][N][N*10];int fx[4] = {0, 0, 1, -1};int fy[4] = {1, -1, 0, 0};int m, n;map<char, int> key;struct node { int x, y, cnt, sta; node():cnt(0), sta(0) {}};queue<node> que;int bfs(int sx, int sy, int ex, int ey) { while(!que.empty()) que.pop(); node tmp; tmp.x = sx, tmp.y = sy; que.push(tmp); while(!que.empty()) { node p = que.front(); if(p.x == ex && p.y == ey) { return p.cnt; } que.pop(); for(int i = 0; i < 4; ++i) { int newx = p.x + fx[i]; int newy = p.y + fy[i]; if(newx < 0 || newx >= m || newy < 0 || newy >= n) continue; if(mz[newx][newy] == '0') continue; int sta = p.sta; if(mz[p.x][p.y] >= 'a' && mz[p.x][p.y] <= 'z') { sta |= (1<<key[mz[p.x][p.y]]); } if(vis[newx][newy][sta]) continue; if(mz[newx][newy] >= 'A' && mz[newx][newy] <= 'Z') { if((sta & (1<<(key[mz[newx][newy] - 'A' + 'a'])))== 0) { continue; } } vis[newx][newy][sta] = true; tmp.x = newx, tmp.y = newy, tmp.cnt = p.cnt + 1, tmp.sta = sta; que.push(tmp); } } return -1;}int main() { while(~scanf("%d %d", &m, &n)) { int sx, sy, ex, ey; int cnt = 0; for(int i = 0; i < m; ++i) { scanf("%s", mz[i]); for(int j = 0; j < n; ++j) { if(mz[i][j] == '2') { sx = i, sy = j; } if(mz[i][j] == '3') { ex = i, ey = j; } if(mz[i][j] >= 'a' && mz[i][j] <= 'z') { key[mz[i][j]] = cnt++; } } } for(int i = 0; i < m; ++i) { for(int j = 0; j < n; ++j) { for(int s = 0; s < (1<<cnt); ++s) { vis[i][j][s] = false; } } } int Ans = bfs(sx, sy, ex, ey); printf("%d/n", Ans); } return 0;}希望本文所述對大家C++程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
