LC 1787. 使所有区间的异或结果为零

题目描述

这是 LeetCode 上的 1787. 使所有区间的异或结果为零 ,难度为 困难

给你一个整数数组 nums 和一个整数 k
区间 [left, right]``(left <= right)的 异或结果 是对下标位于 leftright(包括 leftright )之间所有元素进行 XOR 运算的结果:nums[left] XOR nums[left+1] XOR ... XOR nums[right]

返回数组中要更改的最小元素数 ,以使所有长度为 k 的区间异或结果等于零。

示例 1:

1
2
3
4
5
输入:nums = [1,2,0,3,0], k = 1

输出:3

解释:将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]

示例 2:
1
2
3
4
5
输入:nums = [3,4,5,2,1,7,3,4,7], k = 3

输出:3

解释:将数组 [3,4,5,2,1,7,3,4,7] 修改为 [3,4,7,3,4,7,3,4,7]

示例 3:
1
2
3
4
5
输入:nums = [1,2,4,1,2,5,1,2,6], k = 3

输出:3

解释:将数组[1,2,4,1,2,5,1,2,6] 修改为 [1,2,3,1,2,3,1,2,3]

提示:

  • 1 <= k <= nums.length <= 2000
  • 0 <= nums[i] < $2^{10}$

基本分析

题目示例所包含的提示过于明显了,估计很多同学光看三个样例就猜出来了:答案数组必然是每 $k$ 个一组进行重复的。

这样的性质是可由「答案数组中所有长度为 $k$ 的区间异或结果为 $0$」推导出来的:

  • 假设区间 $[i, j]$ 长度为 $k$,其异或结果为 $0$。即 $nums[i] ⊕ nums[i + 1] ⊕ … ⊕ nums[j] = 0$

  • 长度不变,将区间整体往后移动一位 $[i + 1, j + 1]$,其异或结果为 $0$。即 $nums[i + 1] ⊕ … ⊕ nums[j] ⊕ nums[j + 1] = 0$

  • 两式结合,中间 $[i + 1, j]$ 区间的数值出现两次,抵消掉最终剩下 $nums[i] ⊕ nums[j + 1] = 0$,即推出 $nums[i]$ 必然等于 $num[j + 1]$。

即答案数组必然每 $k$ 个一组进行重复。

也可以从滑动窗口的角度分析:窗口每滑动一格,会新增和删除一个值。对于异或而言,新增和删除都是对值本身做异或,因此新增值和删除值相等(保持窗口内异或值为 $0$)。

因此我们将这个一维的输入看成二维,从而将问题转化为:使得最终每列相等,同时「首行」的异或值为 $0$ 的最小修改次数。

image.png

当然 $n$ 和 $k$ 未必成倍数关系,这时候最后一行可能为不足 $k$ 个。这也是为什么上面没有说「每行异或结果为 $0$」,而是说「首行异或结果为 $0$」的原因:

image.png


动态规划

定义 $f[i][xor]$ 为考虑前 $i$ 列,且首行前 $i$ 列异或值为 $xor$ 的最小修改次数,最终答案为 $f[k - 1][0]$。

第一维的范围为 $[0, k)$,由输入参数给出;第二维为 $[0, 2^{10})$,根据题目给定的数据范围 0 <= nums[i] < 2^10 可得(异或为不进位加法,因此最大异或结果不会超过 $2^{10}$)。

为了方便,我们需要使用哈希表 $map$ 记录每一列的数字分别出现了多少次,使用变量 $cnt$ 统计该列有多少数字(因为最后一行可能不足 $k$ 个)。

不失一般性的考虑 $f[i][xor]$ 如何转移:

  • 当前处于第 $0$ 列:由于没有前一列,这时候只需要考虑怎么把该列变成 $xor$ 即可:
  • 当前处于其他列:需要考虑与前面列的关系。

    我们知道最终的 $f[i][xor]$ 由两部分组成:一部分是前 $i - 1$ 列的修改次数,一部分是当前列的修改次数。

    这时候需要分情况讨论:

    • 仅修改当列的部分数:这时候需要从哈希表中遍历已存在的数,在所有方案中取 $min$:

    • 对整列进行修改替换:此时当前列的修改成本固定为 $cnt$,只需要取前 $i - 1$ 列的最小修改次数过来即可:

最终 $f[i][xor]$ 在所有上述方案中取 $min$。为了加速「取前 $i - 1$ 列的最小修改次数」的过程,我们可以多开一个 $g[]$ 数组来记录前一列的最小状态值。

代码:

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
class Solution {
public int minChanges(int[] nums, int k) {
int n = nums.length;
int max = 1024;
int[][] f = new int[k][max];
int[] g = new int[k];
for (int i = 0; i < k; i++) {
Arrays.fill(f[i], 0x3f3f3f3f);
g[i] = 0x3f3f3f3f;
}
for (int i = 0, cnt = 0; i < k; i++, cnt = 0) {
// 使用 map 和 cnt 分别统计当前列的「每个数的出现次数」和「有多少个数」
Map<Integer, Integer> map = new HashMap<>();
for (int j = i; j < n; j += k) {
map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
cnt++;
}
if (i == 0) { // 第 0 列:只需要考虑如何将该列变为 xor 即可
for (int xor = 0; xor < max; xor++) {
f[0][xor] = Math.min(f[0][xor], cnt - map.getOrDefault(xor, 0));
g[0] = Math.min(g[0], f[0][xor]);
}
} else { // 其他列:考虑与前面列的关系
for (int xor = 0; xor < max; xor++) {
f[i][xor] = g[i - 1] + cnt; // 整列替换
for (int cur : map.keySet()) { // 部分替换
f[i][xor] = Math.min(f[i][xor], f[i - 1][xor ^ cur] + cnt - map.get(cur));
}
g[i] = Math.min(g[i], f[i][xor]);
}
}
}
return f[k - 1][0];
}
}

  • 时间复杂度:共有 $O(C k)$ 个状态需要被转移(其中 $C$ 固定为 $2^{10}$),每个状态的转移需要遍历哈希表,最多有 $\frac{n}{k}$ 个数,复杂度为 $O(\frac{n}{k})$。整体复杂度为 $O(C n)$
  • 空间复杂度:$O(C * k)$,其中 $C$ 固定为 $2^{10} + 1$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1787 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。