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

标签: 位运算 数组 动态规划

难度: Hard

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

Submission

运行时间: 1659 ms

内存: 16.2 MB

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mx = 1 << max(nums).bit_length()
        dp0 = [n] * mx
        dp0[0] = 0
        premin = 0
        for i in range(k):
            cnt = defaultdict(int)
            for j in range(i, n, k):
                cnt[nums[j]] += 1
            m = (n-i-1) // k + 1
            dp1 = [n] * mx
            for x in range(mx if i < k-1 else 1):
                if (tmp := premin+m) < dp1[x]:
                    dp1[x] = tmp
                for y, c in cnt.items():
                    if (tmp := dp0[x^y]+m-c) < dp1[x]:
                        dp1[x] = tmp
            dp0 = dp1
            premin = min(dp0)
        return dp0[0]

Explain

本题解采用动态规划的方法来解决问题。动态规划数组dp[x]表示使得长度为k的区间异或结果为x时，必须修改的最小元素数量。初始时，除了dp[0]为0（表示不需要修改就可以使得异或结果为0），其他dp[x]值均设为n（最大可能的修改次数）。遍历数组中的元素，利用哈希表cnt统计在同一个位置模k的所有元素的出现次数。对于每个可能的异或结果x，计算使其变为0的最小修改次数。这涉及两种情况：一种是直接将当前位置的所有元素修改为使得异或结果为x，另一种是利用已有的异或结果进行转换。通过比较这两种情况，更新dp数组。最后，dp[0]即为所求的最小修改次数。

时间复杂度: O(n * 256)

空间复杂度: O(n/k)

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mx = 1 << max(nums).bit_length()  # 计算2的幂，覆盖所有nums中的值
        dp0 = [n] * mx  # 初始化dp数组，除dp[0]外，全部设为n
        dp0[0] = 0
        premin = 0
        for i in range(k):
            cnt = defaultdict(int)
            for j in range(i, n, k):
                cnt[nums[j]] += 1  # 统计每个值的出现次数
            m = (n-i-1) // k + 1  # 计算当前位置模k的元素数量
            dp1 = [n] * mx
            for x in range(mx if i < k-1 else 1):  # 非最后一轮处理所有x，最后一轮只处理x=0
                if (tmp := premin+m) < dp1[x]:
                    dp1[x] = tmp  # 直接修改所有当前位置模k的元素
                for y, c in cnt.items():
                    if (tmp := dp0[x^y]+m-c) < dp1[x]:
                        dp1[x] = tmp  # 利用已有的dp值和频率更新
            dp0 = dp1
            premin = min(dp0)
        return dp0[0]  # 返回最小修改次数使得所有k长度区间异或结果为0

Explore

在动态规划数组dp[x]中，x代表的是异或结果。dp[x]表示如果我们希望通过修改数组中的元素，使得某个长度为k的区间的异或结果为x时，需要进行的最小修改次数。因此，dp[x]的值就是达到这个异或结果x所需的最小操作数。

初始化时，dp[0]设置为0，因为如果区间的异或结果已经是0，则不需要进行任何修改。其他的dp[x]（其中x不等于0）初始化为n，这代表在最坏的情况下，可能需要修改区间内所有的元素来达到异或结果x。这个初始化确保了在动态规划过程中，任何未经探索的异或结果都有一个最高的修改代价，从而可以在后续的迭代中被实际需要的更小的修改次数所更新。

哈希表cnt在算法中用于统计每个位置模k的所有元素的出现次数。这是因为题目中的区间是固定长度k，并且要求修改元素使得每个长度为k的区间的异或结果为0。通过统计每个位置模k的元素频率，可以有效地计算出哪些元素需要被替换以最小化修改次数。cnt表的角色在于帮助确定最频繁出现的元素，从而减少需要修改的元素数量，以此达到异或结果为0的目的。

在算法中，更新dp数组的两种方法如下：1. 直接修改：这种方法考虑将所有当前位置模k的元素直接修改为一个特定值，以使得异或结果变为x。具体实现时，对于每个x，计算直接修改所有元素到达异或结果x的总成本，即为`premin + m`，其中m是当前位置模k的元素数量，premin是前一轮中dp数组的最小值。2. 利用已有的异或结果进行转换：这种方法考虑利用数组中已经存在的值，通过异或操作转换到目标异或结果x。具体实现时，对于每个可能的y值和它的出现次数c，计算`dp0[x^y] + m - c`，其中`x^y`是通过异或y得到x的结果。这种方法利用了数组中已存在的异或结果，通过修改较少的元素数来达到目标x。这两种方法在每轮迭代中都被计算，然后选择其中的最小值作为新的dp[x]值。