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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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] < 2¹⁰

# 思路

贪心 + dp

# 解法

class Solution {
    public int minChanges(int[] nums, int k) {
        int n = (nums.length / k) + (nums.length % k == 0 ? 0 : 1);
        int[] all = new int[k];
        Arrays.fill(all, nums.length / k);
        
        for(int i=0;i<nums.length%k;i++)
            all[i] ++;
        
        int[][] count = new int[k][1024];
        for(int i=0;i<nums.length;i++)
            count[i%k][nums[i]] ++;
        
        int[][] dp = new int[k][1024];
        //init
        for(int i=0;i<1024;i++)
            dp[0][i] = count[0][i] == 0 ? 50000 : all[0] - count[0][i];
        
        for(int i=1;i<k;i++){
            Arrays.fill(dp[i], 50000);
            for(int j=0;j<1024;j++){
                if(count[i][j] == 0)continue;
                for(int p=0;p<1024;p++){
                    dp[i][j^p] = Math.min(dp[i][j^p], dp[i-1][p] + all[i] - count[i][j]);
                }
            }
        }
        //greedy
        int res = 0, minMaxi = Integer.MAX_VALUE;
        for(int i=0;i<k;i++){
            int maxi = 0;
            for(int j : count[i])
                maxi = Math.max(maxi, j);
            res += all[i] - maxi;
            minMaxi = Math.min(minMaxi, maxi);
        }
        return Math.min(dp[k-1][0], res + minMaxi);
    }
}

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
38
39

# 总结

分析出几种情况，然后分别对各个情况实现

#Java