第六章 - 高频考题(困难)
1787. 使所有区间的异或结果为零

题目地址(1787. 使所有区间的异或结果为零)

题目描述

给你一个整数数组 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

前置知识

  • 异或
  • 动态规划

公司

  • 暂无

常规 DP

思路

题目提到了:
区间 [left, right] 的异或和为 nums[left] XOR nums[left+1] XOR ... XOR nums[right]
你可以转化任意位置上的数字到任意值,求所有长度为 k 个的子数组异或和都为 0 的最小的改变次数。
不难知道两点:
  1. 1.
    解的上限是 n,其中 n 为数组长度。
  2. 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)$

优化的 DP

思路

上面的解法时间复杂度为 $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

情况二: 将 nums[j] 改为分组中已有的数

这种情况我们可以枚举分组中所有的值 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。
Could not load image