美团3.9笔试

#美团##春招#
签到200
第三题 数组前缀合 100 可以参考力扣304。
第四题 用的前缀和做的,复杂度应该在nlogn,为什么只能通过70%的用例,有兄弟知道吗? 
经评论区提醒,应该结果是longlong,难受
简单写一下思路,有多少个0,就是看有多少个5和2。我这里把2和5的数量简写为presum了。
如何看删除区间呢?例如,我们对0.....l.....r.....n-1,删除其中的l-r部分,那么剩余2和5的数量应该是
presum[n-1]-presum[r]+presum[l-1];
那么对于以y为结尾的区间,有多少个合法的删除区间呢?
如果presum[n-1]-presum[y]>=k,那么显然,0到y,1到y,.....y-1到y,y都是合法区间。
如果把presum[n-1]-presum[y]=k,那么x到y,x+1到y.....y-1到y,都是合法区间,也就是需要找到合适的x。
由于presum数组是递增的,因此可以利用二分查找的方式找到x(但是我第一遍用遍历,复杂度On2时间好像也没超)
整体时间复杂度是n(遍历以y结尾的区间)✖️logn(二分查找x的位置)=nlogn。
第五题 不会 10 
经评论区提醒,倒叙作操作,把删边操作转化为增边操作,就可以用并查集解决了。
380够吗,能进面试吗
全部评论
不清楚,都过完了,第五题倒序加并查集就行,倒序就是增边了
13 回复 分享
发布于 03-09 12:06 江苏
220 每人比我更菜
5 回复 分享
发布于 03-09 12:13 江苏
340更寄 好想死
4 回复 分享
发布于 03-09 12:09 湖北
我是算法**,为什么第二道一直超时啊😭😭
3 回复 分享
发布于 03-09 12:10 上海
第四题最后结果要开long long
2 回复 分享
发布于 03-09 12:04 北京
第二题16.7第二题暴力16.7😢,太菜了不想玩辣
1 回复 分享
发布于 03-09 12:19 安徽
满分不是100吗,编程一道20
1 回复 分享
发布于 03-09 12:23 美国
第二题有用java写过的吗?貌似很多人都和我一样是16.67超时。来个人一起讨论一下是哪个地方卡时间了😳😳
1 回复 分享
发布于 03-09 12:26 上海
我也380,😂
点赞 回复 分享
发布于 03-09 12:04 江苏
一样380……
点赞 回复 分享
发布于 03-09 12:05 美国
第五题10分怎么得的哇😭
点赞 回复 分享
发布于 03-09 12:06 上海
第二题怎么做的
点赞 回复 分享
发布于 03-09 12:08 北京
第三题不是平衡矩阵吗,可以细说一下怎么做出来的吗
点赞 回复 分享
发布于 03-09 12:13 广东
第四题怎么做,删除区间,剩余元素乘积末尾0的数量大于等于K
点赞 回复 分享
发布于 03-09 12:15 江苏
同380,分数的分布一毛一样
点赞 回复 分享
发布于 03-09 12:16 广东
请问像二维前缀和类似的算法知识要去哪里系统地学习啊
点赞 回复 分享
发布于 03-09 12:21 北京
你们在哪看分数的啊
点赞 回复 分享
发布于 03-09 12:22 广东
怎么全是⑨爷
点赞 回复 分享
发布于 03-09 12:26 陕西
满分不是100吗??在哪里看分数
点赞 回复 分享
发布于 03-09 12:32 浙江
二维前缀数组去哪里学一下呀..><好菜啊自己
点赞 回复 分享
发布于 03-09 12:33 广东

相关推荐

2 11 评论
分享
牛客网
牛客企业服务