练习题-使所有区间的异或结果为零

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

解析：

设数组 

nums 的长度为 $n$n。  首先我们需要分析出数组 

$$
\textitnums   在修改之后应当具有哪些性质。

由于任意长度为 

k    的区间异或结果等于 0，那么对于任意的 i，有：

nums[i]⊕nums[i+1]⊕⋯⊕nums[i+k−1]=0             （1）

以及：

nums[i+1]⊕nums[i+2]⊕⋯⊕nums[i+k]=0             （2）

其中 

 $\oplus$⊕    表示异或运算。根据异或运算的性质 

a⊕b⊕b=a，将 $(1)(2)$(1)(2)

两式联立，即可得到：

nums[i]⊕nums[i+k]=0

其等价于

nums[i]=nums[i+k]。  因此我们可以得出一个重要的结论：

数组 

nums   在修改之后是一个以

k    为周期的周期性数组，即

$$
\forall i \in [0, n-k), \textit[i] = \textit[i+k]∀i∈[0,n−k),nums[i] 

=nums[i+k]。

因此，我们可以将数组 

nums   按照下标对

k    取模的结果 

$$
0, 1, \cdots, k-10,1,⋯,k−1   分成 

k    个组，每个组内的元素必须要相等，并且这 

k   个组对应的元素的异或和为 

$$
00  ，即：

nums[0]⊕nums[1]⊕⋯⊕nums[k−1]=0

只要满足上述的要求，修改后的数组的所有长度为 

k   的区间异或结果一定等于 

$$
00  。

对于第 

i  个组，我们可以使用哈希映射来存储该组内的元素以及每个元素出现的次数，这样一来，我们就可以尝试使用动态规划来解决本题了。

设 

 $$f(i, \textit)f(i,mask)  表示我们已经处理了第

 $0, 1, \cdots, i$0,1,⋯,i  个组，并且这些组对应元素的异或和：

nums[0]⊕nums[1]⊕⋯⊕nums[i]

为 

mask   的前提下，这些组总计最少需要修改的元素个数。在进行状态转移时，我们可以枚举第 

i  组被修改成了哪个数。假设其被修改成了 

x  ，那么第 

0,1,⋯,i−1    个组对应的元素的异或和即为

mask⊕x  ，因此我们可以得到状态转移方程：

f(i,mask)=xmin{f(i−1,mask⊕x)+size(i)−count(i,x)}

 $$\text(i)size(i)    表示第 

i  个组里的元素个数，

count(i,x)   表示第 

i  个组里元素 

x  的次数，它们的值都可以通过哈希映射得到。上述状态转移方程的意义即为：如果我们选择将第 

i  组全部修改为 

x  ，那么有 

count(i,x)  个数是无需修改的，这样就需要修改 

size(i)−count(i,x)   次。

动态规划的时间复杂度是多少呢？我们发现这并不好估计，这是因为 

x  可以很小，也可以很大，它并没有一个固定的范围。然而我们可以发现，题目中规定了 

nums[i] 

<210
，也就是 

nums[i]   

的二进制表示的位数不超过  

10  。因此我们可以断定，

x  的上限就是 

210。

如果 

x≥210
，那么 

x  的二进制表示的最高位 

1  是在数组 

 $$\textitnums   的其它元素中没有出现过的，因此根据异或的性质，要想将最终的异或结果变为 

$$
00  ，我们需要将另一个组的所有元素改为 

y   ，且 

y   有与 

x  相同的高位 

$$
11  。这样一来，我们不如将 

x  和 

y   的高位 

$$
11  移除，让它们都在

[0,210)  的范围内，这样更容易增大 

count(i,x)  ，减少最终的修改次数。

当我们确定了 

x  的上限，就可以计算出动态规划的时间复杂度了。状态的数量有 $k \times 2^{10}$k×210 个，对于每一个状态，我们需要枚举 

x  来进行状态转移，而 

x   的数量同样有 

210   个，因此时间复杂度为 

O(220k)=O(220n)，  数量级约为 

 $2 \times 10^9$2×109 超出了时间限制，因此我们必须要进行优化。

优化

对于未优化的状态转移方程：

f(i,mask)=xmin{f(i−1,mask⊕x)+size(i)−count(i,x)}

class Solution {
    // x 的范围为 [0, 2^10)
    static final int MAXX = 1 << 10;
    // 极大值，为了防止整数溢出选择 INT_MAX / 2
    static final int INFTY = Integer.MAX_VALUE / 2;

    public int minChanges(int[] nums, int k) {
        int n = nums.length;
        int[] f = new int[MAXX];
        Arrays.fill(f, INFTY);
        // 边界条件 f(-1,0)=0
        f[0] = 0;
        
        for (int i = 0; i < k; ++i) {
            // 第 i 个组的哈希映射
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            int size = 0;
            for (int j = i; j < n; j += k) {
                cnt.put(nums[j], cnt.getOrDefault(nums[j], 0) + 1);
                ++size;
            }

            // 求出 t2
            int t2min = Arrays.stream(f).min().getAsInt();

            int[] g = new int[MAXX];
            Arrays.fill(g, t2min);
            for (int mask = 0; mask < MAXX; ++mask) {
                // t1 则需要枚举 x 才能求出
                for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
                    int x = entry.getKey(), countx = entry.getValue();
                    g[mask] = Math.min(g[mask], f[mask ^ x] - countx);
                }
            }
            
            // 别忘了加上 size
            for (int j = 0; j < MAXX; ++j) {
                g[j] += size;
            }
            f = g;
        }

        return f[0];
    }
}