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够吗，能进面试吗
全部评论
人才池是我家
东南大学 Java
不清楚，都过完了，第五题倒序加并查集就行，倒序就是增边了
土豆茄子豆角
门头沟学院 C++
220 每人比我更菜
给个鸡会球球了
门头沟学院 Java
340更寄 好想死
更寄 好想死 JwJw_
上海大学 Java
我是算法**，为什么第二道一直超时啊😭😭
星际流火
北京大学 C++
第四题最后结果要开long long
JwJw_
上海大学 Java
第二题有用java写过的吗？貌似很多人都和我一样是16.67超时。来个人一起讨论一下是哪个地方卡时间了😳😳
不想上网课的中国人在创作
门头沟学院 测试开发
满分不是100吗，编程一道20
Lighthearte
合肥工业大学 Java
第二题16.7第二题暴力16.7😢，太菜了不想玩辣
梧之风 楼主
楼主 门头沟学院 Java
如果把presum[n-1]-presum[y]=k,那么x到y，x+1到y.....y-1到y，都是合法区间，也就是需要找到合适的x。这里的=应该是<，打错了，不知道为什么不能再次编辑了。
rofgmd
华南理工大学 C++
二维前缀数组去哪里学一下呀..><好菜啊自己
牛客71494248号
浙江大学 推荐算法
满分不是100吗？？在哪里看分数
fermion67
西安电子科技大学 后端
怎么全是⑨爷
在投简历的话题终结者很想提桶
深圳职业技术学院 C++
你们在哪看分数的啊
皮卡超人
华中科技大学 算法工程师
请问像二维前缀和类似的算法知识要去哪里系统地学习啊
牛客933827907号
算法工程师
同380，分数的分布一毛一样
，分数的分布一毛一样 y给我发offer
门头沟学院 算法工程师
第四题怎么做，删除区间，剩余元素乘积末尾0的数量大于等于K
g_oat
中山大学 C++
第三题不是平衡矩阵吗，可以细说一下怎么做出来的吗
白月光111
蚌埠坦克学院 算法工程师
第二题怎么做的
你包有offer的
门头沟学院 Java
第五题10分怎么得的哇😭
躺平了的大白菜很勤劳
University of California San Diego Java
一样380……
相关推荐
07-11 15:12
门头沟学院 Java 
程序员小白条：实习就是摸鱼，只是公司指标，把你进来了，可能那时候客户很多，但等你进来的时候，已经是淡季了，根本没多少需求，或者说根本不适合实习生去完成，因此你就每天干坐着就行，可能1,2个月都没需求
点赞 评论 收藏
分享
06-20 18:53
莆田学院 Java 点赞 评论 收藏
分享