leetcode 1787. 使所有区间的异或结果为零（困难/dp）

本文正在参加「Java主题月 – 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]

题目分析

假设有x1 x2 x3 x4 x5 k=3

根据题意可得x1^x2^x3=x2^x3^x4=x3^x4^x5=0
可以推出x1=x4 x2=x5 x3=x6 ……

所以我们只需要使得x1^x2^x3==0即可，因为x1=x4 所以将其代入得x4^x2^x3=0，就能使得第二个子数组的结果也为0了。我们只需要确定前k个数，就能把后面整个数组都确定了，并且后面的每个子数组都是满足异或结果为0的。

动态规划

现在问题是需要使得x1^x2^x3==0，并且对数组的更改次数是最少的

数组定义

使用dp[i][j]记录—使得前i个数字异或结果为j的最小更换次数
i的取值范围0,k-1，j的取值范围0,1024
最终的结果就是dp[k-1][0]

状态转移

可以通过map记录每个数字出现的次数，从而计算出修改了nums[i]以后整个数组需要的修改次数
cnt[i]记录下前i+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]);
                }
复制代码

异或的结果就是第一个数字的本身，所以只需要减去该异或结果出现的次数，就能得出需要更换的次数

当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];
    }
}
复制代码