[LeetCode周赛复盘] 第 326 场周赛20230101

一、本周周赛总结

• 紧张了 sum写成了len
• T1 模拟。
• T2 大顶堆模拟。
• T3 哈希表，但是两层。
• T4 换根DP。
  

8039. 使数组成为递增数组的最少右移次数

8039. 使数组成为递增数组的最少右移次数

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:
    def minimumRightShifts(self, nums: List[int]) -> int:
        n = len(nums)
        def ok(a):
            return all(x<y for x,y in pairwise(a)) 
        if ok(nums):return 0
        for i in range(1,n):
            if ok(nums[-i:] + nums[:-i]):
                return i
        return -1
1
2
3
4
5
6
7
8
9
10

100020. 删除数对后的最小数组长度

100020. 删除数对后的最小数组长度

1. 题目描述

2. 思路分析

• 其实就是每次消除两个不同的数，那么优先消除更多的数。
• 用大顶堆储存计数即可。
• 可惜最后应该sum剩余的，写成了len

3. 代码实现

class Solution:
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        h = [-v for v in Counter(nums).values()]
        heapify(h)
        while len(h) >= 2:
            x = -heappop(h)
            y = -heappop(h)
            x -= 1 
            y -= 1 
            if x:heappush(h,-x)
            if y:heappush(h,-y)
        return -sum(h)
1
2
3
4
5
6
7
8
9
10
11
12
13

6988. 统计距离为 k 的点对

6988. 统计距离为 k 的点对

1. 题目描述

2. 思路分析

• 本质是哈希表计数，但是多了一维。
• 然而里边那层范围是100，所以可以暴力处理，枚举一个数，计算另一个即可。

3. 代码实现

class Solution:
    def countPairs(self, coordinates, k):
        d = Counter()
        ans = 0
        for x, y in coordinates:
            for j in range(k + 1):
                t1 = x ^ j
                t2 = y ^ (k - j)
                kk = (t1 << 32) | t2                
                ans += d[kk]
            d[(x << 32) | y] += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12

100041. 可以到达每一个节点的最少边反转次数

100041. 可以到达每一个节点的最少边反转次数

1. 题目描述

2. 思路分析

• 又考换根DP了。
• 储存边，计算时看看当前换根的那条边的转向计算即可。

---

• 这题是CF219D,我写换根模板时用的。。直接CV了。

3. 代码实现

class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        g = [[] for _ in range(n)]
        s = set()
        for u,v  in edges:
            g[u].append(v)
            g[v].append(u)
            s.add((u, v))
        f = [0] * n
        fas = [-1] * n
        order = []
        q = deque([0])
        while q:
            u = q.popleft()
            order.append(u)
            for v in g[u]:
                if v == fas[u]: continue
                fas[v] = u
                q.append(v)

        for u in order[::-1]:
            for v in g[u]:
                if v == fas[u]: continue
                f[u] += f[v] + int((v, u) in s)
        for u in order:
            for v in g[u]:
                if v == fas[u]: continue
                f[v] = f[u] + int((u, v) in s) - int((v, u) in s)
        return f       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

参考链接