1787. 使所有区间的异或结果为零
https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/
给你一个整数数组 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] < 210
- 异或
- 动态规划
- 暂无
题目提到了：
区间 [left, right] 的异或和为 nums[left] XOR nums[left+1] XOR ... XOR nums[right]
你可以转化任意位置上的数字到任意值，求所有长度为 k 个的子数组异或和都为 0 的最小的改变次数。
不难知道两点:
- 1.解的上限是 n，其中 n 为数组长度。
- 2.转化后的 nums 数组满足 nums[i] == nums[i+k]，其中 0 <= i < n - k。这是由于异或的自反性决定的。
于是我们可以定义状态 dp[i][j] 为处理到数组第 i 项， 且异或和为 j 的最小操作次数。之后可以通过动态规划来求解。
接下来，我们考虑 dp[i][j] 如何由之前的状态转过来。
由于我们可以选择将 nums[i] 修改为值 val（val 为符合题目限制条件的任意值），使得异或和为 j，那么 修改前的异或值就是 val ^ j (仍然是异或的自反性)。最后只需要考虑将 nums[i] 修改为 val 的操作数（代价）即可。
推上面的第二条知识，将 nums[i] 修改为 val 会同时影响索引满足 i % k 的所有值。比如你将 nums[0] 改成了 val，那么相应需要将 nums[k], nums[2 * k], nums[3 * k] 统统改为 val。 为了叙述方便，我们将 i % k 相同的称为一组，其编号为 i % k。 这样一来，代价就是 a - b。其中 a 为分组数，b 为分组上值为 val 的个数。说人话就是分组中需要被改变的值（本来就是 val 了就不用改了）。
令 val ^ j 为 p，那么有：
dp[i][j] = min(dp[i-1][p] + size[i] - a)，其中 p 为任意满足题目范围的值。
其中 size_i 为
n // k + int(n % k > i)， a 则可以预处理出来，具体参考下方代码。根据上面的公式。我们需要枚举所有的 i，j，p，三层循环就出来了。
- 异或的自反性
- 对值域（upper） 做 dp，而不是数组索引。
- 语言支持：Python3
Python3 Code:
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
counter = collections.defaultdict(int)
UPPER = 2 ** 10
n = len(nums)
for i, num in enumerate(nums):
counter[(i % k, num)] += 1
dp = [[n] * UPPER for _ in range(k)]
for i in range(k):
size_i = n // k + int(n % k > i)
for j in range(UPPER):
for p in range(UPPER):
if i == 0:
dp[i][j] = size_i - counter[(i, j)]
else:
dp[i][j] = min(
dp[i][j],
dp[i - 1][p] + size_i - counter[(i, p ^ j)],
)
return dp[-1][0]
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n * (k+upper^2))$
- 空间复杂度：$O(k * upper)$
注意到 dp[i][j] 仅仅依赖 dp[i-1][...] ，这提示我们使用滚动数组进行优化。由于 p 可能大于 j，因此至少需要两个 dp 数组，而不是一个。
- 语言支持：Python3
Python3 Code:
counter = collections.defaultdict(int)
UPPER = 2 ** 10
n = len(nums)
for i, num in enumerate(nums):
counter[(i % k, num)] += 1
dp = [n] * UPPER
for i in range(k):
size_i = n // k + int(n % k > i)
nxt_dp = [n] * UPPER
for j in range(UPPER):
for p in range(UPPER):
if i == 0:
nxt_dp[j] = size_i - counter[(i, j)]
else:
nxt_dp[j] = min(
nxt_dp[j],
dp[p] + size_i - counter[(i, p ^ j)],
)
dp = nxt_dp
return dp[0]
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n * (k+upper^2))$
- 空间复杂度：$O(upper)$
上面的解法时间复杂度为 $O(n * (k+upper^2))$。代入题目的数据范围大概是 $10 ^ 9$，远远大于 $10^7$，很可能会超时。因此必须优化。
为什么是 $10^7$？不清楚的可以看下这里 https://lucifer.ren/blog/2020/12/21/shuati-silu3/
上面枚举 p 的部分其实是可以优化掉的。核心点是：
- 异或的自反性
- 从改成新的数和改成已有的数角度考虑
对于数组每一位，其实我们都有两种选择：
- 将 nums[j] 改为分组中没有的数
- 将 nums[j] 改为分组中已有的数
情况一：将 nums[j] 改为分组中没有的数
如果将 nums[j] 改为分组中没有的数，那么答案就是
min(dp) + size_i，这是因为我们可以任意选择 dp 中的一项,假设其值为 x，那么我们可以将分组上的数全部改为 x^j，这样就得到了异或和 j。这样的操作代价就是 dp[q] + size_i，其中 0 <= q < upper 。由于我们求的是最小值，那自然就是 min(dp) + size_i。这种情况我们可以枚举分组中所有的值 val，并令 count 为 该分组下 val 的出现次数。那么有：
for val, count in counter[i].items(): # 改成这一列已有的数
nxt_dp[j ^ val] = min(nxt_dp[j ^ val], dp[j] + size_i - count)
- 从改成新的数和改成已有的数角度考虑
- 语言支持：Python3
Python3 Code:
class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
counter = collections.defaultdict(lambda: collections.defaultdict(int))
UPPER = 2 ** 10
n = len(nums)
for i, num in enumerate(nums):
counter[i % k][num] += 1
dp = [n] * UPPER
dp[0] = 0
for i in range(k):
size_i = n // k + int(n % k > i)
nxt_dp = [min(dp) + size_i] * UPPER # 改成新的数
for j in range(UPPER):
for val, count in counter[i].items(): # 改成这一列已有的数
nxt_dp[j ^ val] = min(nxt_dp[j ^ val], dp[j] + size_i - count)
dp = nxt_dp
return dp[0]
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n * (k+upper))$
- 空间复杂度：$O(upper)$
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 8mo ago