[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. 元素值大于变化阈值的子数组
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