2024-03-09 12:34 已编辑 门头沟学院 Java
关注
美团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，使得presum[n-1]-presum[y]+presum[x]>=k,那么x到y，x+1到y.....y-1到y，都是合法区间，也就是需要找到合适的x。
由于presum数组是递增的，因此可以利用二分查找的方式找到x（但是我第一遍用遍历，复杂度On2时间好像也没超）
整体时间复杂度是n(遍历以y结尾的区间)✖️logn(二分查找x的位置)=nlogn。
第五题 不会 10
经评论区提醒，倒叙作操作，把删边操作转化为增边操作，就可以用并查集解决了。
380够吗，能进面试吗
签到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，使得presum[n-1]-presum[y]+presum[x]>=k,那么x到y，x+1到y.....y-1到y，都是合法区间，也就是需要找到合适的x。
由于presum数组是递增的，因此可以利用二分查找的方式找到x（但是我第一遍用遍历，复杂度On2时间好像也没超）
整体时间复杂度是n(遍历以y结尾的区间)✖️logn(二分查找x的位置)=nlogn。
第五题 不会 10
经评论区提醒，倒叙作操作，把删边操作转化为增边操作，就可以用并查集解决了。
380够吗，能进面试吗
全部评论
人才池是我家
美团_后端开发(准入职员工)
不清楚，都过完了，第五题倒序加并查集就行，倒序就是增边了
找苏州软开
门头沟学院 C++
220 每人比我更菜
给个鸡会球球了
携程_后端开发
340更寄 好想死
更寄 好想死 JwJw_
上海大学 Java
我是算法**，为什么第二道一直超时啊😭😭
星际流火
北京大学 C++
第四题最后结果要开long long
Lighthearte
合肥工业大学 Java
第二题16.7第二题暴力16.7😢，太菜了不想玩辣
不想上网课的中国人在创作
门头沟学院 测试开发
满分不是100吗，编程一道20
JwJw_
上海大学 Java
第二题有用java写过的吗？貌似很多人都和我一样是16.67超时。来个人一起讨论一下是哪个地方卡时间了😳😳
在等offer的安哥拉兔很冷艳
门头沟学院 算法工程师
我也380，😂
躺平了的大白菜很勤劳
University of California San Diego Java
一样380……
你包有offer的
字节跳动_后端开发(准入职员工)
第五题10分怎么得的哇😭
白月光111
蚌埠坦克学院 算法工程师
第二题怎么做的
g_oat
中山大学 C++
第三题不是平衡矩阵吗，可以细说一下怎么做出来的吗
y给我发offer
门头沟学院 算法工程师
第四题怎么做，删除区间，剩余元素乘积末尾0的数量大于等于K
牛客933827907号
算法工程师
同380，分数的分布一毛一样
，分数的分布一毛一样 皮卡超人
华中科技大学 算法工程师
请问像二维前缀和类似的算法知识要去哪里系统地学习啊
在投简历的话题终结者很想提桶
深圳职业技术学院 C++
你们在哪看分数的啊
fermion67
西安电子科技大学 后端
怎么全是⑨爷
牛客71494248号
浙江大学 推荐算法
满分不是100吗？？在哪里看分数
rofgmd
华南理工大学 C++
二维前缀数组去哪里学一下呀..><好菜啊自己
相关推荐
胖墩墩的查理在学c语言：哥们我是五号面的 流程差不多
查看21道真题和解析 点赞 评论 收藏
分享
投递美团等公司9个岗位 >