讨论/题目交流/🏆 第 176 场力扣周赛/
🏆 第 176 场力扣周赛

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

image.png

3 分 - 统计有序矩阵中的负数
5 分 - 最后 K 个数的乘积
5 分 - 最多可以参加的会议数目
6 分 - 多次求和构造目标数组

展开讨论

感觉这次变难了。 T3 都那么难。 T4居然自己还没思路。

最后二十分钟AC了。 真是神助。

T1: 签到题
直接搜索或者用一个指针搜索都行。 数据范围很小, 随便过。

时间复杂度O(nm)O(nm) 或 O(n+m)O(n + m).
空间复杂度O(1)O(1)

T2:
这次的T2开始难度就有一些了。
因为数组中可能有0, 所以不能简单用前缀积来做。需要更改一下做法。
还是开前缀数组。 记录的是从上一个非0数到该数的乘积。
按照题意扫描。 每次碰到0则把前缀积变为1然后继续做。 记录最后一个0的位置, 当最后k个元素超过0的位置时可以直接输出0,否则用前缀数组来做。

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

T3:
这道题我没想到简单一点的算法。按天数采取一种贪心算法可以对。
考虑每一天, 因为一天只能参加一个会议。 所以如果那天有会议在召开, 则选择结束时间较早的会议。 这样可以使后面的天数中有更多选择, 答案不会变差。
因此, 维护当前正在召开的会议即可达到这个目的。 先把会议按照起始时间排序, 依次枚举每一天。 如果那一天恰好是某会议的开始时间则把它加入“当前正在召开的会议”。 然后从中选出一个离结束时间最近的来参加。
显然, 简单最标记会超时, 使用优先队列优化即可通过本题。

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

T4
做了T3再来做T4就感觉没那么难了。
考虑倒推法。 因为每个数都是正数, 所以数组的和必然大于每个数。 所以, 当我们得到一个操作后的数组可以还原到操作前的数组。

因此, 算法如下:

  1. 先找出最大的数。 若最大的数为1, 返回true.
  2. 将最大的数减去其他所有数之和。如果该数为0或者负, 返回false.
  3. 将原来最大的数用2中得到数替换。

@ottff 提出如果数据是[1e9, 1]的话, 会超时。 因此, 记录最大和次大数。 每一次看最大的数能够减多少次会比次大数小。 然后一并减掉就可以了。 这种一定要注意边界情况。

经过优化后, 每个数操作后一定会少于其原来的一半。 因此, 针对每个数的操作最多O(logV)O(logV)次, 因此不会超时。

时间复杂度O(nlog(max(ai)))O(nlog(max(a_i)))
空间复杂度O(1)O(1)

13
展开全部 24 讨论