如何抽象成二维问题进行求解｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

题目描述

这是 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}$

基本分析

题目示例所包含的提示过于明显了，估计很多同学光看三个样例就猜出来了：答案数组必然是每 $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$ 的最小修改次数。

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

动态规划

定义 $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$ 即可：