[LeetCode周赛复盘] 第 339场周赛20230402

一、本周周赛总结

• 把昨晚上的分还回去了。
• T1 DP。
• T2 贪心模拟。
• T3 贪心。
• T4 用有序数组/并查集优化BFS转移。

二、 [Easy] 2609. 最长平衡子字符串

链接: 2609. 最长平衡子字符串

1. 题目描述

2. 思路分析

• 应该暴力的。强行DP，边界没考虑好，wa3次。

3. 代码实现

class Solution:def findTheLongestBalancedSubstring(self, s: str) -> int:n = len(s)if n == 1:return 0ans = 0f = [0]*nif s[0] == '0':f[0] = 1for i in range(1,n):if s[i] == '0':f[i] = f[i-1]+1g = [0]*nif s[-1] == '1':g[-1] = 1if f[n-2]>=1:ans = max(ans,2)for i in range(n-2,0,-1):if s[i] == '1':g[i] = g[i+1] + 1# print(f,g)if f[i-1]:ans = max(ans,min(f[i-1],g[i])*2)        return ans

三、[Medium] 2610. 转换二维数组

链接: 2610. 转换二维数组

1. 题目描述

2. 思路分析

• 答案长度是显然的，就是max(cnt[v])，即数目最多的那个数，必须分散在不同的组里。
• 然后把其余的数分散到这些组里即可。

3. 代码实现

class Solution:def findMatrix(self, nums: List[int]) -> List[List[int]]:n = len(nums)cnt = Counter(nums)mx = max(cnt.values())ans = [[] for _ in range(mx)]for k,v in cnt.items():for i in range(v):ans[i].append(k)return ans

四、[Medium] 2611. 老鼠和奶酪

链接: 2611. 老鼠和奶酪

1. 题目描述

2. 思路分析

• 贪心。
• 由于每块奶酪必会被吃掉。因此如果让A吃，而不是B吃，获得的收益是r1-r2。
• 按照r1-r2排序，取收益最大的k个数让A吃即可。

3. 代码实现

class Solution:def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int:n = len(reward1)a = list(zip(reward1,reward2))a.sort(key=lambda x:x[0]-x[1],reverse=True)ans = 0for x,_ in a[:k]:ans += xfor _,y in a[k:]:ans += y return ans        

五、[Hard] 2612. 最少翻转操作数

链接: 2612. 最少翻转操作数

1. 题目描述

2. 思路分析

• 大致思路是建图跑BFS。
• 转移的操作是翻转，手玩一下发现是一个连续段范围内的，公差2的等差数列。
• 计算一下边界:
  • 左边界有两种情况:
    • 以u为右端点长为k的段翻转的位置，则有:
      • x = u-k+1,因为只能翻转到左边。
    • 以0为左端点长为k的段，则有：
      • x-0=k-1-u(其中段上左右边界和四个点是0,x,u,k-1)
      • 计算得x=k-1-u
    • 因此左边界mn=max(u-k+1,k-1+u)。
  • 同理计算右边界两种情况:
    • 以u为左边界的段:
      • x = u + k - 1
    • 以n-1为右边界的段,有:
      • x-(n-1-k+1) = n-1-u
      • 解得:x=2n-k-1-u
    • 右边界mx=min(u+k-1,2n-k-1-u)。
• 转移方案计算出来后，发现如果BFS暴力转移，由于每次要枚举长为2k的段，复杂度就是O(nk)，会TLE。要想办法优化转移。
• 这题由于每次转移的目标是连续的，且访问过一次就不需要再访问了(最短路边权是1)，因此可以考虑有平衡树(有序集合)/并查集维护目标状态。
  • 有序集合(需要支持二分查找):
    • 二分找到目标左右边界，把尚存的范围内目标状态加入队列，从集合中删掉。这样下次再来找，就不会有这些数字了，目标状态一共n个，均摊复杂度O(1)，但二分要O(n)。因此总体是O(nlogn)。
  • 并查集：
    • 一个常用技巧了，如果要删除中间一段，且下次访问可以直接跳过省去遍历，则把i和i+1合并，访问i就直接去下一个了。
    • 认为并查集操作是O(1)的话，均摊总体复杂度是O(n)
• 注意实现时，要分奇偶性储存剩余合法目标状态。

• 并查集用一个就行了，不需要俩。只需要保证操作时别夸着操作就行。
• 

3. 代码实现

from sortedcontainers import SortedListclass DSU:def __init__(self, n):self.fathers = list(range(n))self.size = [1] * n  # 本家族sizeself.edge_size = [0] * n  # 本家族边数(带自环/重边)self.n = nself.setCount = n  # 共几个家族def find_fa(self, x):fs = self.fatherst = xwhile fs[x] != x:x = fs[x]while t != x:fs[t], t = x, fs[t]return xdef union(self, x: int, y: int) -> bool:x = self.find_fa(x)y = self.find_fa(y)if x == y:self.edge_size[y] += 1return False# if self.size[x] > self.size[y]:  # 注意如果要定向合并x->y，需要干掉这个；实际上上边改成find_fa后，按轶合并没必要了，所以可以常关#     x, y = y, xself.fathers[x] = yself.size[y] += self.size[x]self.edge_size[y] += 1 + self.edge_size[x]self.setCount -= 1return Trueclass Solution:def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:ans = [-1] * nans[p] = 0if k == 1:return ansif k == n:if p != n - 1 - p and n - 1 - p not in banned:ans[n - 1 - p] = 1return ansdsu = [DSU(n + 2), DSU(n + 2)]for x in banned:z = dsu[x & 1]z.union(x, x + 2)z = dsu[p & 1]z.union(p, p + 2)q = deque([p])while q:u = q.popleft()d = ans[u] + 1mn = max(u - k + 1, k - u - 1)mx = min(u + k - 1, 2 * n - k - 1 - u)z = dsu[mn & 1]while mn <= mx:mn = z.find_fa(mn)if mn <= mx:ans[mn] = dq.append(mn)z.union(mn, mn + 2)mn += 2# s = [SortedList(range(0, n, 2)), SortedList(range(1, n, 2))]# s[0].discard(p)# s[1].discard(p)# for x in banned:#     s[0].discard(x)#     s[1].discard(x)# q = deque([p])# while q:#     u = q.popleft()#     d = ans[u] + 1#     mn = max(u - k + 1, k - u - 1)#     mx = min(u + k - 1, 2 * n - k - 1 - u)#     p = s[mn & 1]#     l, r = p.bisect_left(mn), p.bisect_right(mx)#     t = p[l:r]#     for x in t:#         ans[x] = d#         q.append(x)#         p.remove(x)return ans      

六、参考链接