题目描述
给你一个整数数组 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 <= 20000 <= nums[i] < 210
解法
方法一：动态规划
注意到数组 nums 在修改之后，任意长度为 $k$ 的区间异或结果都等于 $0$，那么对于任意的 $i$，都有：
$$
nums[i] \oplus nums[i+1] \oplus ... \oplus nums[i+k-1] = 0
$$
以及
$$
nums[i+1] \oplus nums[i+2] \oplus ... \oplus nums[i+k] = 0
$$
结合上面两个等式以及异或运算的性质，可以得到 $nums[i] \oplus nums[i+k] = 0$，即 $nums[i]=nums[i+k]$，我们发现，修改后的数组 nums 中的元素是以周期为 $k$ 的循环，对模 $k$ 同余的一组数必然只能取固定值，同时需要满足前 $k$ 个数异或结果为 $0$。
我们先对每一组 $i$ 进行计数，每一组的元素个数为 $size[i]$，每一组值为 $v$ 的元素个数为 $cnt[i][v]$。
接下来，我们可以用动态规划来求解。设 $f[i][j]$ 表示前 $i+1$ 组异或和为 $j$ 的最小修改次数。由于每一组的值只与前一组的值有关，因此我们可以用滚动数组优化空间复杂度。
重新定义 $f[j]$ 表示处理到当前组，且异或和为 $j$ 的最小修改次数。
状态转移时，有两种选择：一是将当前组的数全部都修改为同一个值，那么我们可以选择上一个代价最小的那个，加上这一组的元素个数 $size[i]$，此时的代价为 $\min{f[0..n]} + size[i]$；二是将当前组的数全部修改为当前组的某个值 $j$，枚举 $j$ 以及当前组的元素 $v$，那么前面的代价为 $f[j \oplus v]$，此时的代价为 $f[j \oplus v] + size[i] - cnt[i][v]$。取最小值即可。
最终答案为 $f[0]$。
时间复杂度 $O(2^{C}\times k + n)$。其中 $n$ 是数组 nums 的长度，而 $C$ 为 nums 中元素二进制表示的最大位数，本题中 $C=10$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | class Solution:
def minChanges(self, nums: List[int], k: int) -> int:
n = 1 << 10
cnt = [Counter() for _ in range(k)]
size = [0] * k
for i, v in enumerate(nums):
cnt[i % k][v] += 1
size[i % k] += 1
f = [inf] * n
f[0] = 0
for i in range(k):
g = [min(f) + size[i]] * n
for j in range(n):
for v, c in cnt[i].items():
g[j] = min(g[j], f[j ^ v] + size[i] - c)
f = g
return f[0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class Solution {
public int minChanges(int[] nums, int k) {
int n = 1 << 10;
Map<Integer, Integer>[] cnt = new Map[k];
Arrays.setAll(cnt, i -> new HashMap<>());
int[] size = new int[k];
for (int i = 0; i < nums.length; ++i) {
int j = i % k;
cnt[j].merge(nums[i], 1, Integer::sum);
size[j]++;
}
int[] f = new int[n];
final int inf = 1 << 30;
Arrays.fill(f, inf);
f[0] = 0;
for (int i = 0; i < k; ++i) {
int[] g = new int[n];
Arrays.fill(g, min(f) + size[i]);
for (int j = 0; j < n; ++j) {
for (var e : cnt[i].entrySet()) {
int v = e.getKey(), c = e.getValue();
g[j] = Math.min(g[j], f[j ^ v] + size[i] - c);
}
}
f = g;
}
return f[0];
}
private int min(int[] arr) {
int mi = arr[0];
for (int v : arr) {
mi = Math.min(mi, v);
}
return mi;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 | class Solution {
public:
int minChanges(vector<int>& nums, int k) {
int n = 1 << 10;
unordered_map<int, int> cnt[k];
vector<int> size(k);
for (int i = 0; i < nums.size(); ++i) {
cnt[i % k][nums[i]]++;
size[i % k]++;
}
vector<int> f(n, 1 << 30);
f[0] = 0;
for (int i = 0; i < k; ++i) {
int mi = *min_element(f.begin(), f.end());
vector<int> g(n, mi + size[i]);
for (int j = 0; j < n; ++j) {
for (auto& [v, c] : cnt[i]) {
g[j] = min(g[j], f[j ^ v] + size[i] - c);
}
}
f = move(g);
}
return f[0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | func minChanges(nums []int, k int) int {
n := 1 << 10
cnt := make([]map[int]int, k)
for i := range cnt {
cnt[i] = map[int]int{}
}
size := make([]int, k)
for i, v := range nums {
cnt[i%k][v]++
size[i%k]++
}
f := make([]int, n)
for i := 1; i < n; i++ {
f[i] = 0x3f3f3f3f
}
for i, sz := range size {
g := make([]int, n)
x := slices.Min(f) + sz
for i := range g {
g[i] = x
}
for j := 0; j < n; j++ {
for v, c := range cnt[i] {
g[j] = min(g[j], f[j^v]+sz-c)
}
}
f = g
}
return f[0]
}
|