题目描述
这是 LeetCode 上的 1787. 使所有区间的异或结果为零 ，难度为 困难。
Tag : 「线性 DP」、「异或」、「数学」
给你一个整数数组 nums 和一个整数 k 。 区间 [left, right]``（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right ）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right] 。
返回数组中要更改的最小元素数 ，以使所有长度为 k 的区间异或结果等于零。
示例 1：
输入：nums = [1,2,0,3,0], k = 1 输出：3 解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0] 复制代码
示例 2：
输入：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：
输入：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}210
基本分析
题目示例所包含的提示过于明显了，估计很多同学光看三个样例就猜出来了：答案数组必然是每 kk 个一组进行重复的。
这样的性质是可由「答案数组中所有长度为 kk 的区间异或结果为 00」推导出来的：
- 假设区间 [i, j][i,j] 长度为 kk，其异或结果为 00。即 nums[i] ⊕ nums[i + 1] ⊕ ... ⊕ nums[j] = 0nums[i]⊕nums[i+1]⊕...⊕nums[j]=0
- 长度不变，将区间整体往后移动一位 [i + 1, j + 1][i+1,j+1]，其异或结果为 00。即 nums[i + 1] ⊕ ... ⊕ nums[j] ⊕ nums[j + 1] = 0nums[i+1]⊕...⊕nums[j]⊕nums[j+1]=0
- 两式结合，中间 [i + 1, j][i+1,j] 区间的数值出现两次，抵消掉最终剩下 nums[i] ⊕ nums[j + 1] = 0nums[i]⊕nums[j+1]=0，即推出 nums[i]nums[i] 必然等于 num[j + 1]num[j+1]。
即答案数组必然每 kk 个一组进行重复。
也可以从滑动窗口的角度分析：窗口每滑动一格，会新增和删除一个值。对于异或而言，新增和删除都是对值本身做异或，因此新增值和删除值相等（保持窗口内异或值为 00）。
因此我们将这个一维的输入看成二维，从而将问题转化为：使得最终每列相等，同时「首行」的异或值为 00 的最小修改次数。
当然 nn 和 kk 未必成倍数关系，这时候最后一行可能为不足 kk 个。这也是为什么上面没有说「每行异或结果为 00」，而是说「首行异或结果为 00」的原因：
动态规划
定义 f[i][xor]f[i][xor] 为考虑前 ii 列，且首行前 ii 列异或值为 xorxor 的最小修改次数，最终答案为 f[k - 1][0]f[k−1][0]。
第一维的范围为 [0, k)[0,k)，由输入参数给出；第二维为 [0, 2^{10})[0,210)，根据题目给定的数据范围 0 <= nums[i] < 2^10 可得（异或为不进位加法，因此最大异或结果不会超过 2^{10}210）。
为了方便，我们需要使用哈希表 mapmap 记录每一列的数字分别出现了多少次，使用变量 cntcnt 统计该列有多少数字（因为最后一行可能不足 kk 个）。
不失一般性的考虑 f[i][xor]f[i][xor] 如何转移:
- 当前处于第 00 列：由于没有前一列，这时候只需要考虑怎么把该列变成 xorxor 即可：
f[0][xor] = cnt - map.get(xor)f[0][xor]=cnt−map.get(xor)
- 当前处于其他列：需要考虑与前面列的关系。我们知道最终的f[i][xor]f[i][xor]由两部分组成：一部分是前i - 1i−1列的修改次数，一部分是当前列的修改次数。这时候需要分情况讨论：
- 仅修改当列的部分数：这时候需要从哈希表中遍历已存在的数，在所有方案中取 minmin：
- f[i][xor] = f[i - 1][xor ⊕ cur] + cnt - map.get(cur)f[i][xor]=f[i−1][xor⊕cur]+cnt−map.get(cur)
- 对整列进行修改替换：此时当前列的修改成本固定为 cntcnt，只需要取前 i - 1i−1 列的最小修改次数过来即可：
- f[i][xor] = f[i - 1][xor'] + cntf[i][xor]=f[i−1][xor′]+cnt
最终 f[i][xor]f[i][xor] 在所有上述方案中取 minmin。为了加速「取前 i - 1i−1 列的最小修改次数」的过程，我们可以多开一个 g[]g[] 数组来记录前一列的最小状态值。
代码：
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)O(C∗k) 个状态需要被转移（其中 CC 固定为 2^{10}210），每个状态的转移需要遍历哈希表，最多有 \frac{n}{k}kn 个数，复杂度为 O(\frac{n}{k})O(kn)。整体复杂度为 O(C * n)O(C∗n)
- 空间复杂度：O(C * k)O(C∗k)，其中 CC 固定为 2^{10} + 1210+1
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1787 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
