本文实例讲述了基于C++的拼多多算法在线笔试题。分享给大家供大家参考,具体如下: 最近在狼厂实习中,很久没做题了。秋招第一发, 拼多多。。。 四个简单题,看到有些人竟然觉
本文实例讲述了基于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++程序设计有所帮助。