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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。