2024-03-09 美团笔试 430/500

  • 第一题 100%(签到)
  • 1e5长度的字符串,k次修改次数,最多可以让字符串有多少'M','T'字符
  • 不是'M'或'T'的话改就行,直到k用完
  • 第二题 100% (签到)
  • 1e5长度的正整数数组,其中有部分元素为0,1e5次询问,每次给L和R,问0元素全部改成该区间范围内某元素后,数组的和最大、最小为多少
  • 记一下0的数量,显然把0全变成L最小,变成R最大
  • 第三题 100% (二维前缀和)
  • 大小为200的01方阵,从1到n输出答案,答案为大小为i的方阵中01数量相等的方阵有多少
  • 直接暴力会T,用二维前缀和记一下
  • 第四题 30% (看评论区老哥解法学会了)
  • 大小为1e5的正整数数组,有多少种删除区间的方案,使得剩下元素的乘积末尾0至少为k个
  • 直接枚举区间范围暴力,能过30%
  • 第五题 100% (离线 + 反向并查集)
  • 编号为1e9的人,有1e5对朋友关系,朋友关系能够间接传递;1e5次询问,询问包含:1、删除一对直接朋友关系 2、询问两个人是否能通过朋友关系认识,对于2的询问输出Yes或No
  • 并查集支持合并与栈形式的撤销合并操作,对于本题无序的删边,需要用到离线
  • 最开始只合并操作中没有删除的边,然后从询问反着依次查询以及合并
  • 一些边界条件:
  • 可能会重复删除,记得只保存第一次删除的,同时,非直接关系需要忽略
  • 保存边的时候要保存无向图,如{u, v},应该保存{u, v}和{v, u}
  • 点的大小为1e9,并查集数组需要用哈希表来存,预先把所有点存下来再初始化
#美团笔试#
全部评论
第五题 全部打印Yes怒骗3分
24 回复 分享
发布于 2024-03-09 12:40 山东
第四题预先计算所有 2 因子和 5 因子的数量,然后计算出一个 maximum delete 2 和 5(最多能删除的个数)。然后你 for 循环,维护一个前缀的 2 因子的数量和 5 因子的数组。对这个数组做二分可以找到对于当前索引 i 往左最多能删除的区间长度,ans += 这个区间长度即可。注意维护下数组就行了。
7 回复 分享
发布于 2024-03-09 12:08 广东
只a两个能进面吗....麻了
4 回复 分享
发布于 2024-03-09 12:36 陕西
T4 顺手重写了下大概是这样
3 回复 分享
发布于 2024-03-09 12:50 广东
第四题想用滑动窗口做,剩二十分钟没写完,太久没写题了第三题改bug改疯了
2 回复 分享
发布于 2024-03-09 12:12 上海
不知道为什么前两题一样的写法 为啥只有 40 和16的通过率
2 回复 分享
发布于 2024-03-09 12:06 湖北
第四题我是先全部乘起来,然后动态规划一个个除掉,但只过了30%,感觉可能是数组里有0的原因,最后来不及改了
2 回复 分享
发布于 2024-03-09 12:06 上海
第二题不知道为啥怎么改都是30%..
2 回复 分享
发布于 2024-03-09 12:03 四川
佬,能看看为啥我的并查集只能过3个样例吗,我思路感觉和你的一样呀🥺
1 回复 分享
发布于 2024-03-12 14:16 北京
2题16.777(golang,int)是什么鬼...离谱哎
1 回复 分享
发布于 2024-03-09 12:18 浙江
A了四道加第五道dfs骗了百分之10,第四道我是算每个数的2和5的因子个数的前缀和。然后再双指针遍历以每个i结尾的删除区间
1 回复 分享
发布于 2024-03-09 12:14 北京
我想问哪里可以找到这期的java答案?
点赞 回复 分享
发布于 2024-03-14 05:50 江苏
m
点赞 回复 分享
发布于 2024-03-12 22:50 安徽
第四题o(n)双指针: #include <bits> using namespace std; typedef long long ll; const int N=100010; int a[N],n,k; int s1[N],s2[N],a1[N],a2[N]; ll res; bool check(int i,int j) { int cnt1=s1[j]-s1[i-1],cnt2=s2[j]-s2[i-1]; int lft=min(s1[n]-cnt1,s2[n]-cnt2); return lft>=k; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>k; for(int i=1;i<=n;i++) { int x,t; cin>>x; t=x; while(x%2==0) a1[i]++,x/=2; x=t; while(x%5==0) a2[i]++,x/=5; } for(int i=1;i<=n;i++) { s1[i]=a1[i]+s1[i-1]; s2[i]=a2[i]+s2[i-1]; } for(int j=1,i=1;j<=n;j++) { while(i<=j&&!check(i,j)) i++; res+=j-i+1; } cout<<res><<"\n"; return 0; }</res></bits>
点赞 回复 分享
发布于 2024-03-12 12:24 黑龙江
T5啥叫离线处理?学习一下
点赞 回复 分享
发布于 2024-03-11 01:16 北京
第四题可以使用回溯:找子集-过滤有已删除元素的子集
点赞 回复 分享
发布于 2024-03-10 15:31 上海
点赞 回复 分享
发布于 2024-03-09 17:36 广东
410,只骗到了10分,悲
点赞 回复 分享
发布于 2024-03-09 14:36 浙江
有没有朋友能提供第5题的代码参考一下,并查集忘得差不多了
点赞 回复 分享
发布于 2024-03-09 14:19 浙江
第五题只能弗洛伊德骗分个10了每次查找都复制一边二维数组然后重新弗洛伊德,结局就是爆内存
点赞 回复 分享
发布于 2024-03-09 14:15 广东

相关推荐

咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
被普调的六边形战士很高大:项目经历貌似和专业或者求职方向没大关系?
点赞 评论 收藏
分享
评论
47
101
分享

创作者周榜

更多
牛客网
牛客企业服务