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

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

前言

整体评价

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

T1 分割数组

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

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

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

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

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

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

class Solution:    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:        ans = 0        n = 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 ) ) O(log(m)) O(log(m))

class Solution:    def earliestSecondToMarkIndices(self, nums, changeIndices) -> int:        n, m = len(nums), len(changeIndices)        s = sum(nums)        def check(end):            last_t = [-1] * n            for i, x in enumerate(changeIndices[:end]):                last_t[x-1] = i             if -1 in last_t:                return False                        cnt = 0            for i, x in enumerate(changeIndices[:end]):                 idx = x - 1                if i == last_t[idx]:                    if cnt  bool:            slow = total            cnt = 0            h = []            for i in range(mx-1, -1, -1):                idx = changeIndices[i] - 1                v = nums[idx]                if i != ft[idx] or v