力扣第 386 场周赛解题报告

力扣第 386 场周赛解题报告 | 反悔贪心

前言

在这里插入图片描述

整体评价

前两天发烧，今天才补完题（非常惭愧）第三题的二分不容易想到，第四题的 “反悔堆” 这种思想值得学习。

T1 分割数组

思路：通过哈希表保证不存在出现两次以上的数即可。

时间复杂度： $O (n)$

class Solution:def isPossibleToSplit(self, nums: List[int]) -> bool:cnt = Counter()for x in nums:cnt[x] += 1if (cnt[x] > 2):return Falsereturn True

T2 求交集区域内的最大正方形面积

思路：交集左下角纵坐标为两个矩形左下角纵坐标的最大值，右上角纵坐标为两个矩形右上角纵坐标的最小值。排序遍历求解。

时间复杂度： $O(n^2)$

class Solution:def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:ans = 0n = len(bottomLeft)z = zip(bottomLeft, topRight)z = sorted(z)bottomLeft, topRight = zip(*z)for i in range(n):for j in range(i + 1, n):x1, y1 = max(bottomLeft[i][0], bottomLeft[j][0]), max(bottomLeft[i][1], bottomLeft[j][1])x2, y2 = min(topRight[i][0], topRight[j][0]), min(topRight[i][1], topRight[j][1])d = min(x2 - x1, y2 - y1)d = max(d, 0)ans = max(ans, d * d)return ans

(代码丑陋，欢迎批评指正)

T3 标记所有下标的最早秒数 I

思路：二分答案。从左往右遍历，判断是否可以完成任务。

时间复杂度： $O (l o g (m))$

class Solution:def earliestSecondToMarkIndices(self, nums, changeIndices) -> int:n, m = len(nums), len(changeIndices)s = sum(nums)def check(end):last_t = [-1] * nfor i, x in enumerate(changeIndices[:end]):last_t[x-1] = i if -1 in last_t:return Falsecnt = 0for i, x in enumerate(changeIndices[:end]): idx = x - 1if i == last_t[idx]:if cnt < nums[idx]:return False cnt -= nums[idx]else:cnt += 1 return True ans = bisect_left(range(0, m + 1), True, key=check)return ans if ans <= m else -1

T4 标记所有下标的最早秒数 II

思路大致是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受。如此往复。

这道题思维比较大，写的浑浑噩噩，终于改好了。

时间复杂度： $O (m l o g (mn))$

class Solution:def earliestSecondToMarkIndices(self, nums: List[int], changeIndices: List[int]) -> int:n, m = len(nums), len(changeIndices)total = n + sum(nums)ft = [-1] * (n)for i in range(m-1, -1, -1):ft[changeIndices[i]-1] = i# 长度为 mxdef check(mx: int) -> bool:slow = totalcnt = 0h = []for i in range(mx-1, -1, -1):idx = changeIndices[i] - 1v = nums[idx]if i != ft[idx] or v <= 1:cnt += 1continue                if cnt == 0:if not h or v <= h[0]:cnt += 1continue cnt += 2slow += heappop(h) + 1slow -= v + 1cnt -= 1heappush(h, v)return cnt >= slowans = bisect_left(range(0, m+1), True, key=check)return ans if ans < m + 1 else -1