This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

The title

I give you an integer array nums and an integer k. The XOR result of the interval [left, right] (left <= right) is the result of the XOR operation on all elements with subscripts between left and right (including left and right) : nums[left] XOR nums[left+1] XOR … XOR nums [right].

Returns the minimum number of elements in the array to change so that all interval xor of length K results in zero.

Example 1:

Input: nums = [1,2,0,3,0], k = 1 Output: 3 Description: Modify array [1,2,0,3,0] to [0,0,0,0] Example 2:

Input: nums =,4,5,2,1,7,3,4,7 [3], k = 3 output: 3: amend the array,4,5,2,1,7,3,4,7 [3] to [3,4,7,3,4,7,3,4,7] example 3:

Input: nums =,2,4,1,2,5,1,2,6 [1], k = 3 output: 3: amend the array,2,4,1,2,5,1,2,6 [1] to [1,2,3,1,2,3,1,2,3]

Subject analysis

Let’s say I have x1, x2, x3, x4, x5, and k is equal to 3

  • X1 ^x2^x3=x2^x3^x4=x3^x4^x5=0
  • X1 =x4, x2=x5, x3=x6……

So all we have to do is set x1 to the x2 to the x3 to be equal to 0, because x1 is equal to x4 so we plug in x4 to the x2 to the x3 is equal to 0, and that will make the second subarray equal to 0. All we have to do is determine the first k, and then we have the entire array, and every subarray that follows is xor zero.

Dynamic programming

Now the problem is to make x1^x2^x3==0, and make the least number of changes to the array

To define an array

  • Use dp[I][j] to record the minimum number of replacements in which the first I digits are xor j
  • The value range of I is 0,k-1, and j is 0,1024
  • The final result is dp[k-1][0]

State transition

CNT [I] record the minimum number of changes of the first I +1 digit (any XOR result is acceptable)

  1. When dp[I][j] ‘s I =0, it means that the first digit cannot be transferred from the previous one
for (int j=0; j<max; j++) { dp[0][j]=num-map.getOrDefault(j,0); cnt[0]= Math.min(cnt[0],dp[0][j]); }Copy the code

The xor result is the first number itself, so you just subtract the number of times the xor result occurs to get the number of times you need to replace it

  1. When dp [I] [j] I! =0, which means it’s not the first number, it can be transferred from the previous one
for (int j=0; j<max; j++) { dp[i][j]=cnt[i-1]+num; for (Integer integer : map.keySet()) { dp[i][j]=Math.min(dp[i][j],dp[i-1][integer^j]+num-map.get(integer)); } cnt[i]= Math.min(cnt[i],dp[i][j]); }Copy the code

There are two cases. One is the nums [I].. Nums [I +k] dp[I][j]= CNT [i-1]+num; . Dp [I][j]= math.min (dp[I][j],dp[i-1][integer^j]+num-map.get(integer));

code

class Solution {
    public int minChanges(int[] nums, int k) {


         int max=1024,n=nums.length;
        int[][] dp = new int[k][max];
        int[]cnt=new int[k];
        for(int i=0; i<k; i++){ Arrays.fill(dp[i],Integer.MAX_VALUE); cnt[i]=Integer.MAX_VALUE; }for(int i=0; i<k; i++) {int num=0;
            Map<Integer,Integer> map=new HashMap<>();
            for (intj=i; j<n; j+=k) { map.put(nums[j],map.getOrDefault(nums[j],0) +1);
                num++;
            }

            if (i==0) {}else {
                for (int j=0; j<max; j++) { dp[i][j]=cnt[i-1]+num;
                    for (Integer integer : map.keySet()) {
                        dp[i][j]=Math.min(dp[i][j],dp[i-1][integer^j]+num-map.get(integer)); } cnt[i]= Math.min(cnt[i],dp[i][j]); }}}return dp[k-1] [0]; }}Copy the code