[数据结构与算法][LeetCode周赛复盘-补] 第 82 场双周赛20220709

一、本周周赛总结

• 幸好没参加，二三题掉大分。

二、 [Easy] 6090. 极大极小游戏

链接: 6090. 极大极小游戏

1. 题目描述

2. 思路分析

定级Easy。
按题意dfs模拟即可。

3. 代码实现

class Solution:
    def evaluateTree(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if root.val < 2:
                return root.val 
            if root.val == 2:
                return self.evaluateTree(root.left) or self.evaluateTree(root.right)
            else:
                return self.evaluateTree(root.left) and self.evaluateTree(root.right)
        return [False,True][dfs(root)]

三、[Medium] 2332. 坐上公交的最晚时间

链接: 2332. 坐上公交的最晚时间

1. 题目描述

2. 思路分析

定级Medium。
太难了，最后看的题解。

• 计算最后一辆公交车能载的最后一个人。
• 这时如果最后一个公交车有空位，那我可以最后再上。
• 否则就要挤掉最后一个人。
• 因此无论如何，先找到最后一个人，我需要沿着他向前找到第一个空位。
• 特别的，如果最后bus时刻没人来，且bug空，那我直接上。

3. 代码实现

class Solution:
    def latestTimeCatchTheBus(self, buses: List[int], passengers: List[int], capacity: int) -> int:
        n,m = len(buses),len(passengers)
        buses.sort()
        passengers.sort()
        # print(buses)
        # print(passengers)
        ps = set(passengers)
        j=0
        ans = 1
        for i,bus in enumerate(buses):
            c = capacity
            while j < m and c and passengers[j] <= bus:
                c -= 1
                j += 1
        j -= 1
        if c:
            ans = buses[-1]
        else:
            ans = passengers[j]
        while j >= 0 and ans == passengers[j]:
            ans = passengers[j]-1
            j -= 1
            
        return ans

四、[Medium] 2333. 最小差值平方和

链接: 2333. 最小差值平方和

1. 题目描述

2. 思路分析

定级Medium。
这题一开始照着周赛T1思路做，导致最差情况每次只能-1，TLE。
后来调整了思路，前缀和+二分可以过。

• 首先题目转化为共k次(k1+k2)调整，每次使任意一个差减小1，最后求差数组的平方和。
• 因此对差数组diff[]来说，每次操作一定是减小最大的那个数一下。当然这样暴力会TLE。
• 我们对diff数组从大到小排序，考虑每次操作。
• 每次操作都是对最大数操作，把它降低到次大数-1后，就应该再降低次大数了。但如果剩余步数k不够就没办法了。
• 那么如何批量操作呢，考虑最多使用k步，对前边i个操作集体“砍头”，即把前i-1个数一律降低到diff[i]，最多能砍去多少（砍掉的头的和）。
• 显然求出前缀和后这个数=presum[i]-(i+1)*diff[i]，就是三角形面积-低长方体面积。
• 这个函数和k的关系是单调的，因此可以二分。
• 我们二分找到使用最多k的，这个i的位置。
• 最后计算如果要砍到这个位置，k不够，可以把不够的部分逐一补回前边diff[0:i]里。
• 这里就要用除法，每次填个平均数，类似微信抢红包算法。

3. 代码实现

class Solution:
    def minSumSquareDiff(self, nums1: List[int], nums2: List[int], k1: int, k2: int) -> int:
        k = k1+k2 
        diff = sorted([abs(a-b) for a,b in zip(nums1,nums2) if a != b], reverse=True ) +[0] 
        n = len(diff)
        presum = list(accumulate(diff))  
        # print(diff)    
        # print(presum)
        def calc(i):  # 把i前边的数都都变成diff[i]，总共要减多少；这个函数返回值随着i增大而增大；我们最多只能减k，因此可以二分
            return presum[i]-(i+1)*diff[i]
        pos = bisect_left(range(n),k,key=calc)
        if pos >= n:
            return 0
        x = diff[pos]
        c = calc(pos)
        diff[:pos] = [x]*pos
        # print(x,k,c,pos,diff)
        s = c - k
        for i in range(pos):
            t = s//(pos-i)
            diff[i] += t 
            s -= t
        
        return sum(a*a for a in diff)

五、[Hard] 2334. 元素值大于变化阈值的子数组

链接: 2334. 元素值大于变化阈值的子数组

1. 题目描述

2. 思路分析

定级Hard。
这题好简单，思考了一会就想到了。

• 实际上是找每个子区间的长度和它里最小的数，逐一按公式判断。
• 那么就很经典的单调栈应用：对每个数作为区间最小值，找出他能管辖的范围左边界left[i]和右边界right[i]。
• 逐一判断即可，复杂度O(n)。

3. 代码实现

class Solution:
    def validSubarraySize(self, nums: List[int], threshold: int) -> int:
        n = len(nums)
        left = [-1] * n 
        stack = []
        for i,v in enumerate(nums):
            while stack and nums[stack[-1]] >= v:
                stack.pop()
            
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        right = [n] * n 
        stack = []
        for i in range(n-1,-1,-1):
            v = nums[i]
            while stack and nums[stack[-1]] >= v :
                stack.pop()

            if stack:
                right[i] = stack[-1]
            stack.append(i)
        
        for i,v in enumerate(nums):
            k = right[i]-left[i]-1
            if v > threshold/k:
                return k 
        return -1