概要
力扣第 369 场周赛
本文只是周赛的总结，我不准备详细地讨论每一道题，只会给出大致思路。重点还是在于自己的总结、反思和提高。
赛后来看，这场比赛难度不大。做题情况简要描述：
- 第一题：简单模拟，送分题；
- 第二题：难度不大，但要考虑多种情况，我没有静下心来细想，造成了 3 个 WA 😒；
- 第三题：难度中等的 DP，一开始没有想出来，转而去做最终没做出来的第四题，浪费了时间。好在后来很快做出来了😋；
- 第四题：虽然是困难题，并且没有做出来，但比赛的代码最终也只是超时，赛后我也自己想出来了优化的方法——不难。值得注意的是，写代码时的逻辑混乱还是造成了 2 个 WA 😒；
题目描述有点难懂，比赛时需要结合示例才能快速读懂
逐比特模拟：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int findKOr(int[] nums, int k) {
int ans = 0;
for (int i = 0; i < 32; i++) {
int count = 0;
int val = 1 << i;
for (int num : nums) {
if ((num & val) > 0) count++;
}
if (count >= k) {
ans |= val;
}
}
return ans;
}
}
|
时间复杂度：$O(n)$
- 如果
nums1 中有 k 个 0，那么它的和在替换后必须要增加至少 k
- 如果
nums1 中至少有一个 0，那么它在替换后的和可以等于任意大于 sum(nums1) 的值
nums2 同理
函数的返回类型为 long；数组长度最大为 $10^5$，元素最大为 $10^6$，数组和最大为 $10^{11}$，超过 32-bit int 的上限。这提醒我们中间步骤的计算结果需要用 long 存储。事实上，算法题应该都用 long 代替 int，避免整数溢出，并且开销也不大。
重点在于判断无法相等的条件，在这上面的失误造成了 3 个 WA：
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
| import java.util.Arrays;
class Solution {
public long minSum(int[] nums1, int[] nums2) {
long sum1 = Arrays.stream(nums1).mapToLong(i -> i).sum();
long sum2 = Arrays.stream(nums2).mapToLong(i -> i).sum();
long c1 = Arrays.stream(nums1).filter(i -> i == 0).count();
long c2 = Arrays.stream(nums2).filter(i -> i == 0).count();
if (sum1 > sum2) {
if (c2 == 0) return -1;
if (c1 == 0 && c2 + sum2 > sum1) return -1;
} else if (sum1 == sum2) {
if (c1 == 0 && c2 != 0) return -1;
if (c1 != 0 && c2 == 0) return -1;
} else {
if (c1 == 0) return -1;
if (c2 == 0 && c1 + sum1 > sum2) return -1;
}
return Math.max(sum1 + c1, sum2 + c2);
}
}
|
如果数组中任何长度 大于或等于 3 的子数组，其 最大 元素都大于或等于 k ，则认为数组是一个 美丽数组 。
上述条件等价于 每个长度为 3 的子数组 中的最大元素都 $\ge k$
很明显，我们应该尽量地使每 3 个连续元素中，有一个元素 $\ge k$。但是应该使哪些元素增加到 $k$ 呢？不清楚，那就用 DP —— 局部暴力解
1️⃣DP定义：dp[i]：使得 nums[0:i] 为美丽数组，并且 nums[i] $\ge k$ 的最小递增运算数。—— 这里有 3 个加粗的重点
nums[i] $\ge k$，那么 nums[i - 2 : i] 这个长度为 3 的子数组肯定能被覆盖，满足美丽数组的条件。这一覆盖同时表明，我们至少需要保证nums[0:(i-3)] 是美丽数组，才能使得 nums[0:i] 成为美丽数组。dp[i - 3]、dp[i - 2]、dp[i - 1] 的结果都可以满足这一点，取最小值值即可：
2️⃣递归式：$dp[i] = \max\set{0,k-nums[i]} + \min\set{dp[i - 1], dp[i - 2], dp[i - 3]}$
3️⃣答案：dp[n - 3]、dp[n - 2] 和 dp[n - 1] 按照定义都可以使 nums 成为美丽数组，取三者最小值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| import java.util.Arrays;
class Solution {
public long minIncrementOperations(int[] nums, int k) {
int n = nums.length;
long[] dp = new long[n];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = Math.max(0, k - nums[0]);
dp[1] = Math.max(0, k - nums[1]);
dp[2] = Math.max(0, k - nums[2]);
for (int i = 3; i < n; i++) {
long v = Math.max(0, k - nums[i]);
dp[i] = Math.min(dp[i], dp[i - 1] + v);
dp[i] = Math.min(dp[i], dp[i - 2] + v);
dp[i] = Math.min(dp[i], dp[i - 3] + v);
}
return Math.min(dp[n - 1], Math.min(dp[n - 2], dp[n - 3]));
}
}
|
1️⃣建树。其实是建图，只是我们要从节点 0 开始 dfs，模拟树遍历的过程
2️⃣收集金币的两个方案（题目故意写得复杂，需要化简）：
- 方案 1：当前收集到的金币加上
coins[i] - k （无论正负）
- 方案 2：
floor(coins[i] / 2) 就是整数除法，需要用位运算优化，即 coins[i] >> 1。位运算还有一个好处，假设当前节点有 $k$ 个祖先节点选择了方案 2，那么该节点的金币数就是 coins[i] >> k，免去了计算和除以 $2^k$ 的开销。
根据这两个方案，我们可以写出一个前序遍历的递归函数：
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
|
private long recur(Node root, long half) {
if (root == null) return 0;
visited[root.index] = true;
long res1 = (root.val >> half) - k;
for (Node child : root.children) {
if (visited[child.index]) continue;
res1 += recur(child, half);
}
long res2 = (root.val >> (1 + half));
for (Node child : root.children) {
if (visited[child.index]) continue;
res2 += recur(child, half + 1);
}
visited[root.index] = false;
return Math.max(res1, res2);
}
|
到这一步为止，我在比赛中都写了出来，但还是超时了。之后，我又想到了如下的优化思路：
3️⃣ $\forall i, coins[i] \le 10^4$ ，并且 $\log_2(10^4) \approx 13.8$ ，因此，只要当前子树的祖先节点选择了至少 14 次方案 2，该子树中的所有节点的金币数都会不断减半至 0
这相当于一个剪枝，在 recur 函数开始处判断：
1
| if (half >= 14) return 0;
|
4️⃣说到递归，就想到分治算法范式，又会联想到 DP 算法范式。两者的区别是什么？—— DP 会复用子问题的结果，因此效率更高。
尽管遍历树的过程没法写成迭代，但我们可以用 map 来缓存子问题的结果：key 是 (nodes[i], half)，value 是收集到的金币数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| private final HashMap<Node, HashMap<Long, Long>> dpMap = new HashMap<>();
private long recur(Node root, long half) {
if (root == null) return 0;
HashMap<Long, Long> mp = dpMap.get(root);
if (mp != null) {
Long ans = mp.get(half);
if (ans != null) return ans;
}
long ans = Math.max(res1, res2);
dpMap.putIfAbsent(root, new HashMap<>());
dpMap.get(root).put(half, ans);
return ans;
}
|
加上了这两步优化，成功 AC 了：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.stream.IntStream;
class Solution {
private static class Node {
List<Node> children = new ArrayList<>();
int val;
int index;
public Node(int val, int index) {
this.val = val;
this.index = index;
}
}
private int k;
private boolean[] visited;
public int maximumPoints(int[][] edges, int[] coins, int k) {
this.k = k;
int n = coins.length;
visited = new boolean[n];
Node[] nodes = IntStream.range(0, n).mapToObj(i -> new Node(coins[i], i)).toArray(Node[]::new);
for (int[] e : edges) {
nodes[e[0]].children.add(nodes[e[1]]);
nodes[e[1]].children.add(nodes[e[0]]);
}
return (int) recur(nodes[0], 0);
}
private final HashMap<Node, HashMap<Long, Long>> dpMap = new HashMap<>();
private long recur(Node root, long half) {
if (half >= 14) return 0;
if (root == null) return 0;
HashMap<Long, Long> mp = dpMap.get(root);
if (mp != null) {
Long ans = mp.get(half);
if (ans != null) return ans;
}
visited[root.index] = true;
long res1 = (root.val >> half) - k;
for (Node child : root.children) {
if (visited[child.index]) continue;
res1 += recur(child, half);
}
long res2 = (root.val >> (1 + half));
for (Node child : root.children) {
if (visited[child.index]) continue;
res2 += recur(child, half + 1);
}
visited[root.index] = false;
long ans = Math.max(res1, res2);
dpMap.putIfAbsent(root, new HashMap<>());
dpMap.get(root).put(half, ans);
return ans;
}
}
|