題目

給你一個整數數組 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]

解題思路

題目分析

假設有x1 x2 x3 x4 x5 k=3

• 根據題意可得x1^x2x3=x2^x3x4=x3^x4x5=0
• 可以推出x1=x4 x2=x5 x3=x6 …
  所以我們只需要使得x1^x2x3==0即可，因為x1=x4 所以將其代入得x4^x2x3=0，就能使得第二個子數組的結果也為0了。我們只需要確定前k個數，就能把后面整個數組都確定了，并且后面的每個子數組都是滿足異或結果為0的。

動態規劃

現在問題是需要使得x1^x2x3==0，并且對數組的更改次數是最少的

數組定義

• 使用dp[i][j]記錄—使得前i個數字異或結果為j的最小更換次數
• i的取值范圍0,k-1，j的取值范圍0,1024
• 最終的結果就是dp[k-1][0]

狀態轉移

可以通過map記錄每個數字出現的次數，從而計算出修改了nums[i]以后整個數組需要的修改次數
cnt[i]記錄下前i+1個數字的最少更換次數（任意的異或結果均可）

1. 當dp[i][j]的i=0,說明是第一個數字，沒辦法從前面的轉移而來

              for (int j=0;j<max;j++){dp[0][j]=num-map.getOrDefault(j,0);cnt[0]= Math.min(cnt[0],dp[0][j]);}

異或的結果就是第一個數字的本身，所以只需要減去該異或結果出現的次數，就能得出需要更換的次數
2. 當dp[i][j]的i!=0,說明不是第一個數字，可以從前面的轉移而來

                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]);}

分為兩種情況。一是將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));

代碼

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 (int j=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];}
}