美团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够吗,能进面试吗
签到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]
由于presum数组是递增的,因此可以利用二分查找的方式找到x(但是我第一遍用遍历,复杂度On2时间好像也没超)
整体时间复杂度是n(遍历以y结尾的区间)✖️logn(二分查找x的位置)=nlogn。
第五题 不会 10
经评论区提醒,倒叙作操作,把删边操作转化为增边操作,就可以用并查集解决了。
380够吗,能进面试吗
全部评论
不清楚,都过完了,第五题倒序加并查集就行,倒序就是增边了
220 每人比我更菜
340更寄 好想死
我是算法**,为什么第二道一直超时啊😭😭
第四题最后结果要开long long
第二题16.7第二题暴力16.7😢,太菜了不想玩辣
满分不是100吗,编程一道20
第二题有用java写过的吗?貌似很多人都和我一样是16.67超时。来个人一起讨论一下是哪个地方卡时间了😳😳
我也380,😂
一样380……
第五题10分怎么得的哇😭
第二题怎么做的
第三题不是平衡矩阵吗,可以细说一下怎么做出来的吗
第四题怎么做,删除区间,剩余元素乘积末尾0的数量大于等于K
同380,分数的分布一毛一样
请问像二维前缀和类似的算法知识要去哪里系统地学习啊
你们在哪看分数的啊
怎么全是⑨爷
满分不是100吗??在哪里看分数
二维前缀数组去哪里学一下呀..><好菜啊自己
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享