LeetCode 题解工作台
使所有区间的异或结果为零
给你一个整数数组 nums 和一个整数 k 。区间 [left, right] （ left ）的 异或结果 是对下标位于 left 和 right （包括 left 和 right ）之间所有元素进行 XOR 运算的结果： nums[left] XOR nums[left+1]…
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
注意到数组 `nums` 在修改之后，任意长度为 的区间异或结果都等于 ，那么对于任意的 ，都有： $$
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个整数数组 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 <= 20000 <= nums[i] < 210
解题思路
方法一：动态规划
注意到数组 nums 在修改之后，任意长度为 的区间异或结果都等于 ，那么对于任意的 ，都有：
以及
结合上面两个等式以及异或运算的性质，可以得到 ，即 ，我们发现，修改后的数组 nums 中的元素是以周期为 的循环，对模 同余的一组数必然只能取固定值，同时需要满足前 个数异或结果为 。
我们先对每一组 进行计数，每一组的元素个数为 ，每一组值为 的元素个数为 。
接下来，我们可以用动态规划来求解。设 表示前 组异或和为 的最小修改次数。由于每一组的值只与前一组的值有关，因此我们可以用滚动数组优化空间复杂度。
重新定义 表示处理到当前组，且异或和为 的最小修改次数。
状态转移时，有两种选择：一是将当前组的数全部都修改为同一个值，那么我们可以选择上一个代价最小的那个，加上这一组的元素个数 ，此时的代价为 ；二是将当前组的数全部修改为当前组的某个值 ，枚举 以及当前组的元素 ，那么前面的代价为 ，此时的代价为 。取最小值即可。
最终答案为 。
时间复杂度 。其中 是数组 nums 的长度，而 为 nums 中元素二进制表示的最大位数，本题中 。
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
n = 1 << 10
cnt = [Counter() for _ in range(k)]
size = [0] * k
for i, v in enumerate(nums):
cnt[i % k][v] += 1
size[i % k] += 1
f = [inf] * n
f[0] = 0
for i in range(k):
g = [min(f) + size[i]] * n
for j in range(n):
for v, c in cnt[i].items():
g[j] = min(g[j], f[j ^ v] + size[i] - c)
f = g
return f[0]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * 2^m) where n is the array length and m is the max bit width of nums elements, due to DP over XOR states for each position group. Space complexity is O(2^m * k) for storing DP tables per group. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice the repeating pattern every k elements; this hints at grouping indices modulo k.
- question_mark
Consider dynamic programming over XOR states; naive brute-force leads to timeouts.
- question_mark
Pay attention to bit width of elements; optimizing DP for feasible states is key.
常见陷阱
外企场景- error
Ignoring the modulo k grouping causes redundant computation and incorrect minimal changes.
- error
Not tracking XOR transitions correctly can lead to overcounting changes.
- error
Assuming segments are independent without considering overlapping indices breaks correctness.
进阶变体
外企场景- arrow_right_alt
Compute minimal changes for segments of varying lengths instead of fixed k.
- arrow_right_alt
Find the number of ways to modify the array to satisfy XOR zero per segment.
- arrow_right_alt
Extend the problem to 2D grids where XOR of subgrids must be zero.