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

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 1787. 使所有区间的异或结果为零原题链接困难

作者：

wzc1995 , 2021-03-07 12:19:15 , 所有人可见 , 阅读 691

题目描述

给你一个整数数组 nums 和一个整数 k。区间 [left, right]（left <= right）的 异或结果 是对下标位于 left 和 right（包括 left 和 right）之间所有元素进行 XOR 运算的结果：nums[left] XOR nums[left+1] XOR ... XOR nums[right]。

返回数组中 要更改的最小元素数，以使所有长度为 k 的区间异或结果等于零。

样例

输入：nums = [1,2,0,3,0], k = 1
输出：3
解释：将数组 [1,2,0,3,0] 修改为 [0,0,0,0,0]。

输入：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]。

输入：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^10

算法

(动态规划) $O(nS)$

可以发现一个规律，最终修改后的数组，一定是每 k 个数字循环出现的。
统计下标 $i \% k$ 中，每个数字的出现次数 $p(i \% k, s)$。至此，我们只需要求出将前 $k$ 位变为一个异或值为 0 的数组的最少修改次数。
设状态 $f(i, j)$ 表示前 $i$ 个下标中，异或值为 $j$ 时的最少修改次数。其中 $i$ 的范围为 $[0, k)$，$j$ 的范围为 $[0, 1024)$。
初始时，$f(0, j) = sum(0)$，$f(0, k) = sum(0) - p(0, k)$。其中 $sum$ 数组为 $i \% k$ 下标的总出现次数。其余为正无穷待定。
转移时
- 对于 $f(i, j)$，首先可以通过全部修改第 $i$ 位来达到，即转移 $f(i, j) = \min(f(i - 1, t)) + sum(i)$。这里 $f(i - 1, t)$ 可以在上一层转移中记录下来（代码中设为 $g$ 数组）。
- 也可以通过这一位上已经有的数字 $k$，从 $f(i - 1, j \text{ xor } k) + sum(i) - p(i, k)$ 进行转移。
最终答案为 $f(k - 1, 0)$。

时间复杂度

假设数组的最大值为 $S$，则状态数为 $O(kS)$，每次转移需要 $O(\frac{n}{k})$ 的时间，故总时间复杂度为 $O(nS)$。

空间复杂度

需要 $O(kS)$ 的空间存储预处理的数组和动态规划的状态。

C++ 代码

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<unordered_map<int, int>> p(k);
        vector<int> sum(k, 0);
        for (int i = 0; i < n; i++) {
            p[i % k][nums[i]]++;
            sum[i % k]++;
        }

        vector<vector<int>> f(k, vector<int>(1024, INT_MAX));
        vector<int> g(k, INT_MAX);
        for (int j = 0; j < 1024; j++) {
            f[0][j] = sum[0];
            g[0] = min(g[0], f[0][j]);
        }

        for (const auto &[k, v] : p[0]) {
            f[0][k] = sum[0] - v;
            g[0] = min(g[0], f[0][k]);
        }

        for (int i = 1; i < k; i++)
            for (int j = 0; j < 1024; j++) {
                f[i][j] = g[i - 1] + sum[i];

                for (const auto &[k, v] : p[i]) {
                    f[i][j] = min(f[i][j], f[i - 1][j ^ k] + sum[i] - v);
                }
                g[i] = min(g[i], f[i][j]);
            }

        return f[k - 1][0];
    }
};

6 评论

仅存老实人 2021-05-25 12:13

wzc大佬,i了i了

simonhan 2021-05-25 11:55

class Solution {
public:
    static constexpr int N = 1 << 10;
    int minChanges(vector<int>& nums, int k) {
        int dp[k][N];
        int g[k];//上一列的最小，用来加速
        int n = nums.size();
        memset(dp,0x3f,sizeof dp);
        memset(g,0x3f,sizeof g);//每一列的最小值
        for(int i = 0;i < k;i++){
            unordered_map<int,int> hash;
            int cnt = 0;
            //这一列的总元素和hash表的构建
            for(int j = i;j < n;j+=k){
                cnt++;
                hash[nums[j]]++;
            }
            //第一列的时候只要知道改变的个数就可以了
            if(i == 0){
                for(int mask = 0;mask < N;mask++){
                    int add = 0;
                    if(hash.count(mask)) add = hash[mask];
                    dp[0][mask] = min(dp[0][mask],cnt - add);
                    g[0] = min(g[0],dp[0][mask]);
                }
            }else{//其余列要求最小，要知道上一列的修改最小，然后状态转移
                for(int mask = 0;mask < N;mask++){
                    dp[i][mask] = g[i - 1] +cnt;
                    for(auto [x,countx]:hash){
                        dp[i][mask] = min(dp[i][mask],dp[i - 1][mask ^ x] + cnt - countx);
                    }
                    g[i] = min(g[i],dp[i][mask]);
                }
            }
        }
        return dp[k - 1][0];
    }
};

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        N = 1 << 10
        INT_MAX = int(2 << 10)
        dp = [[INT_MAX] * N for _ in range(k)]
        g = [INT_MAX] * k
        n = len(nums)
        for i in range(k):
            mp = defaultdict(int)
            cnt = 0
            for j in range(i,n,k):
                cnt += 1
                mp[nums[j]] += 1
            if i == 0:
                for mask in range(0,N):
                    dp[0][mask] = min(dp[0][mask],cnt - mp[mask])
                    g[0] = min(g[0],dp[0][mask])
            else:
                for mask in range(0,N):
                    dp[i][mask] = g[i - 1] + cnt
                    for x,countx in mp.items():
                        dp[i][mask] = min(dp[i][mask],dp[i - 1][mask ^ x] + cnt - countx)
                    g[i] = min(g[i],dp[i][mask])
        return dp[k - 1][0]