讨论/题目交流/🐱 第 19 场夜喵双周赛/
🐱 第 19 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 将数字变成 0 的操作次数
4 分 - 大小为 K 且平均值大于等于阈值的子数组数目
5 分 - 时钟指针的夹角
6 分 - 跳跃游戏 IV

展开讨论

题解来了。

先说一下所有题的看法。

前三题非常水, 第四题有点难。
T1:
直接按题意模拟即可。

T2:
用类似滑动窗口的方法。 先选择前k个元素, 看和是否满足。 然后每一次用队列入队一个, 出队一个再次判断。因为并不需要保留队列本身, 只需要一个队列首尾指针。 空间复杂度可以优化到常数。

时间复杂度O(n)
空间复杂度O(1)

T3:
这道题比T2还容易想一点。
时针每一小时转30度, 每一分钟0.5度。 分针每一分钟6度。直接以12点为基准, 算出两根针转动的角度之差就行了。 注意, 大于180度的时候要用360去减(考虑的是劣角)。

T4:
第四题我用了一种非常zz的优化过了。但是应该过不了所有数据。
该方法是 因为连续相同的数字只有首位两个有用(跳到中间数字相同, 却少了选择, 只能花一步跳到同样的数字, 明显劣于两端的数字)。 因此, 每次连续的数字段只保留首尾。
再BFS过了。

考虑以下数据:
n = 49999, arr = [1,2,3] * 16666 + [4]
n = 49999, arr = [1,2,3] * 8333 + [4,5,6] * 8333 + 7
n = 50000, arr = [1,2] * 25000 + [3,4] * 25000

BFS水过的坐等大家真正的题解!

参考评论区的见解, 以下给出真正的做法。

Step 1. 离散化
原题数据范围很大, 离散化后数据范围变小可以直接取下标,比map快(卡常基本技巧之一)。

Step 2. 连续型优化。
如上面所说, 连续的相同数字只保留首尾。

Step 3. 把这个问题考虑成一个图, 相同的数字和下标相邻的数字都有一条边。 则对所有相同的数字形成的子图是完全图。 这样我们在BFS的时候, 只需要判断每个val是否遍历过。 因为这个图的边没有权值。 一旦在BFS过程中, 一条边作为队首,必定会遍历到该值所有的点。

这样就能如大佬所说的优化到线性了。 当然, 排序是更花时间的。

时间复杂度O(nlogn)
空间复杂度O(n)

3
展开全部 14 讨论