1787. 使所有区间的异或结果为零

题目地址(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
前置知识
异或
动态规划
公司
暂无
常规 DP
思路
题目提到了：
区间 [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)$
优化的 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