狗家VO

匿名者 发表于 2022-2-26 22:54
第四题不能用sliding window吧，如果有负数的话，比如 1,2,3,-6 在读1,2,3时不知道后面的，如果移动left就 ...

同意，负数的话sliding window就失效了。请问如果用prefix sum复杂度是多少呢？有办法比o(n2)好吗？

匿名者 发表于 2022-2-27 00:37
同意，负数的话sliding window就失效了。请问如果用prefix sum复杂度是多少呢？有办法比o(n2)好吗？

我觉得就是O（n^2）必须得每个区间都算和才知道答案

alfiegilbert 发表于 2022-2-26 18:11
请问一下timeline？

VO是1.18

匿名者 发表于 2022-2-26 21:54
第四题不能用sliding window吧，如果有负数的话，比如 1,2,3,-6 在读1,2,3时不知道后面的，如果移动left就 ...

在那一题的context里面数组的每个数字都是距离，所以都是正数~

楼主的timeline可以分享一下吗

第五题也可以用skiplist写，不过考场上感觉还是python的sortedlist方便

请问楼主 第五轮， 如果allowed distance 是 2，如果已经有了6，8，12，14；这时候如果来了个10的话 是把 6个数字都拿走么 （因为都满足了两辆之和小于2）？