基于C++的拼多多算法在线笔试题示例
更新时间:2020年4月25日 17:30 点击:1380
本文实例讲述了基于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++程序设计有所帮助。
上一篇: C++ Coroutine简单学习教程
下一篇: C++ 哈夫曼树对文件压缩、加密实现代码
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要是介绍了.net C# 实现任意List的全组合算法实现代码,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15