0


2022美团校招技术岗笔试全部AC_Code分享

【自动车算法岗】差了5秒钟,终究还是没能AK呀。第三题一开始只对了18%的数据,在还有20分钟的时候,发现题目看错了,码到 cout<<ans<<endl; 的时候发现还剩5秒了,赶紧从ide复制到代码框内,光标刚刚放到保存代码上,发现按不动了,好家伙,时间截止了!!!

笔试题分为两大部分:4道算法题+3道人工智能相关知识的多选题。限时两个小时,每个子部分提交后可以再返回修改,这点还是很人性化的,不像有的笔试,子部分提交后就无法返回修改了,就不是那么的友好了。

题目大概都是力扣 [mid~hard] 的难度,下面切入正题吧!由于晚上还有一场笔试,具体的思路证明之类的以后再补了哈,先贴一下Code


**第一题_四川麻将 **

题意

玩法是摸完牌之后选择3张花色一样的牌按某种顺序换给其他人。为了尽可能破坏对手的游戏体验,每次都会选择不连续的3张牌换出去。比如手上有 {1 4 5 6 8} 这5张条子,则可能会选择 {1 5 8} 这三张条子换出去。
把这个问题进行了简化,现在给你一个可重集合,并希望你从中选出一个尽可能大的子集使得其中没有两个数是 “连续” 的。

输入输出描述

输入

第一行一个整数n(1<=n<=100000),代表可重集大小
第二行n个空格隔开的整数(范围在1到200000之间),代表可重集

输出

输出满足条件的最大子集的大小

样例数据

输入

6

1 2 3 5 6 7

输出

4

AC_Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5+10, M = 2e5+10;
  4. int n, a[N], dp[M];
  5. int main() {
  6. cin>>n;
  7. for(int i=1; i<=n; i++) cin>>a[i];
  8. for(int i=1; i<=n; i++) dp[a[i]] = 1 ;
  9. for(int i=1; i<M; i++) {
  10. if(dp[i]) dp[i] = max(dp[i],dp[i-2]+1);
  11. dp[i] = max(dp[i],dp[i-1]);
  12. }
  13. cout << dp[M-1] << endl;
  14. return 0;
  15. }

第二题_翻转最大子段和

题意

最大子段和是力扣上比较经典问题。这里对它进行了改编,允许在求解该问题之前翻转这个数组的连续一段,如翻转 (1,2,3.45.6) 的第3个到第5个元素组成的子数组得到的是 (1,2,5,4,3,6),求翻转后该数组的最大子段和最大能达到多少。

输入输出描述

输入

第一行—个正整数n,(1<=n<=100000),代表数组长度
第二行n个空格隔开的整数 (-1000<=ai< =1000),代表数组元素大小

输出

求翻转后所得数组的最大子段和

样例数据

输入

6

-1 3 -5 2 -1 3

输出

7

AC_Code

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5+10, inf = 1e9+10;
  4. int n, a[N], p[N], s[N];
  5. void solve() {
  6. p[0] = -inf;
  7. int sum=0;
  8. for(int i=1; i<=n; i++) {
  9. sum = max(0, sum) + a[i];
  10. p[i] = max(p[i-1], sum);
  11. }
  12. s[n+1]=-inf; sum=0;
  13. for(int i=n; i>=1; i--) {
  14. sum = max(0, sum) + a[i];
  15. s[i] = max(s[i+1], sum);
  16. }
  17. }
  18. int main() {
  19. cin>>n;
  20. for(int i=1; i<=n; i++) cin>>a[i];
  21. solve();
  22. int ma = *max_element(p+1, p+n+1);
  23. for(int i=1; i<n; i++)
  24. ma = max(ma, p[i]+s[i+1]);
  25. cout << ma << endl;
  26. return 0;
  27. }

第三题_切豆腐

题意

为了切出更均匀的豆腐,想知道每一次下刀之后切出来的豆腐块中体积最大的那块有多大。

输入输出描述

第一行两个整数n,m (1<=n,m<=1000),代表最开始长宽高均为n厘米,总共切了m刀。
第二行m个小写字母,每个字母都是 x,y,z 中的一个。第i个代表刀垂直于哪个坐标轴。
第三行m个大于0且小于n的正整数。第i个代表第i刀所在平面到豆腐的右上角 (或者任选一个角并固定,无论选哪个角答案均相同) 的距离。
保证切的时候豆腐不会产生形变且不会产生位移。每次下刀都会把整块豆腐切开,不存在切到一半收刀,切出来的每块小豆腐都是边长为正整数的长方体。

样例数据

输入

2 3

x y z

1 1 1

输出

4

2

1

AC_Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5+10, M = 2e5+10;
  4. int n, m;
  5. int main()
  6. {
  7. cin >> n >> m;
  8. vector<string> op(m+1);
  9. for(int i=1; i<=m; i++) cin>>op[i];
  10. vector<int> v(m+1);
  11. for(int i=1; i<=m; i++) cin>>v[i];
  12. multiset<int> x,y,z;
  13. x.insert(0), x.insert(n);
  14. y.insert(0), y.insert(n);
  15. z.insert(0), z.insert(n);
  16. for(int i=1; i<=m; i++)
  17. {
  18. if(op[i][0]=='x') x.insert(v[i]);
  19. else if(op[i][0]=='y') y.insert(v[i]);
  20. else if(op[i][0]=='z') z.insert(v[i]);
  21. }
  22. int mx=0, my=0, mz=0, pre=0;
  23. for(auto it:x) mx = max(mx,it-pre), pre=it;
  24. pre=0;
  25. for(auto it:y) my = max(mx,it-pre), pre=it;
  26. pre=0;
  27. for(auto it:z) mz = max(mx,it-pre), pre=it;
  28. vector<int> ans(m+1);
  29. for(int i=m; i>=1; i--)
  30. {
  31. ans[i] = mx*my*mz;
  32. if(op[i][0]=='x')
  33. {
  34. auto it = x.find(v[i]);
  35. int suf = *(++it);
  36. it--;
  37. int pre = *(--it);
  38. mx = max(mx, suf-pre);
  39. x.erase(v[i]);
  40. }
  41. if(op[i][0]=='y')
  42. {
  43. auto it = y.find(v[i]);
  44. int suf = *(++it);
  45. it--;
  46. int pre = *(--it);
  47. my = max(my, suf-pre);
  48. y.erase(v[i]);
  49. }
  50. if(op[i][0]=='z')
  51. {
  52. auto it = z.find(v[i]);
  53. int suf = *(++it);
  54. it--;
  55. int pre = *(--it);
  56. mz = max(mz, suf-pre);
  57. z.erase(v[i]);
  58. }
  59. }
  60. for(int i=1; i<=m; i++)
  61. cout << ans[i] << endl;
  62. return 0;
  63. }

第四题_区间操作求和

题意

给出一个长度为n的数组,进行m次数组上的区间操作,操作包含将区间内所有数加上一个值和查询一个区间内所有数的和。如果允许重新排列初始数组中的元素并依次进行操作,则操作中所有查询区间和的答案之和能够达到多大?

输入输出描述

输入

第一行有两个数 n,m(1<=n=<5000,1<=m<=500),代表数组长度和操作次数。第二行有n个数,代表初始数组中的元素,接下来m行每行 1 l r 或 2 l r k,分别代表查询下标属于 [l,r] 的元素之和这一揭作和将下标属于 [l,r] 的元素全部加上定值k。l r k 满足1<=l<=r<=n,1<=k<=5000

输出

输出若允许重新排列初始数组,进行m次操作后产生的所有输出之和最大值

样例数据

输入

5 5

3 4 2 1 5

1 1 3

2 3 4 2

1 2 4

2 2 3 2

1 3 5

输出

42

AC_Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5+10, M = 2e5+10;
  4. int n, m;
  5. int main() {
  6. cin>>n>>m;
  7. vector<ll> a(n+1);
  8. for(int i=1; i<=n; i++) cin>>a[i];
  9. ll ans_sum=0;
  10. vector<ll> cnt(n+1),add(n+1);
  11. for(int i=1; i<=m; i++) {
  12. int op; cin>>op;
  13. if(op==1) {
  14. int l,r;
  15. cin>>l>>r;
  16. for(int i=l; i<=r; i++) cnt[i]++, ans_sum += add[i];
  17. }
  18. else{
  19. int l,r,k;
  20. cin>>l>>r>>k;
  21. for(int i=l; i<=r; i++) add[i] += k;
  22. }
  23. }
  24. sort(a.begin()+1,a.end());
  25. sort(cnt.begin()+1,cnt.end());
  26. for(int i=1; i<=n; i++)
  27. ans_sum += 1LL * cnt[i] * a[i];
  28. cout << ans_sum << endl;
  29. return 0;
  30. }

OVER~

标签: 算法 c++ leetcode

本文转载自: https://blog.csdn.net/Luoxiaobaia/article/details/123297413
版权归原作者 米莱虾 所有, 如有侵权,请联系我们删除。

“2022美团校招技术岗笔试全部AC_Code分享”的评论:

还没有评论