題目

給你一個(gè)整數(shù)數(shù)組 nums??? 和一個(gè)整數(shù) k????? 。區(qū)間 [left, right]（left <= right）的 異或結(jié)果 是對(duì)下標(biāo)位于 left 和 right（包括 left 和 right ）之間所有元素進(jìn)行 XOR 運(yùn)算的結(jié)果：nums[left] XOR nums[left+1] XOR … XOR nums[right] 。

返回?cái)?shù)組中 要更改的最小元素?cái)?shù) ，以使所有長(zhǎng)度為 k 的區(qū)間異或結(jié)果等于零。

示例 1：

輸入：nums = [1,2,0,3,0], k = 1
輸出：3
解釋：將數(shù)組 [1,2,0,3,0] 修改為 [0,0,0,0,0]
示例 2：

輸入：nums = [3,4,5,2,1,7,3,4,7], k = 3
輸出：3
解釋：將數(shù)組 [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
解釋：將數(shù)組[1,2,4,1,2,5,1,2,6] 修改為 [1,2,3,1,2,3,1,2,3]

解題思路

題目分析

假設(shè)有x1 x2 x3 x4 x5 k=3

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

動(dòng)態(tài)規(guī)劃

現(xiàn)在問(wèn)題是需要使得x1^x2x3==0，并且對(duì)數(shù)組的更改次數(shù)是最少的

數(shù)組定義

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

狀態(tài)轉(zhuǎn)移

可以通過(guò)map記錄每個(gè)數(shù)字出現(xiàn)的次數(shù)，從而計(jì)算出修改了nums[i]以后整個(gè)數(shù)組需要的修改次數(shù)
cnt[i]記錄下前i+1個(gè)數(shù)字的最少更換次數(shù)（任意的異或結(jié)果均可）

當(dāng)dp[i][j]的i=0,說(shuō)明是第一個(gè)數(shù)字，沒(méi)辦法從前面的轉(zhuǎn)移而來(lái)

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

異或的結(jié)果就是第一個(gè)數(shù)字的本身，所以只需要減去該異或結(jié)果出現(xiàn)的次數(shù)，就能得出需要更換的次數(shù)
2. 當(dāng)dp[i][j]的i!=0,說(shuō)明不是第一個(gè)數(shù)字，可以從前面的轉(zhuǎn)移而來(lái)

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]這個(gè)序列的全部更換為序列以外的元素dp[i][j]=cnt[i-1]+num;。二是用這個(gè)序列里面的某一個(gè)元素替代掉這個(gè)序列 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];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 1787. 使所有区间的异或结果为零的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。