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

目录

题目

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

提示:

1 <= k <= nums.length <= 2000
​​​​​​0 <= nums[i] < 210

思路

一开始我这么想的
举个例子,k=3,那么n[1]^n[2]^n[3] = 0,n[2]^n[3]^n[4] = 0。所以,n[1]=n[4],即n[i]=n[i+k]
假设以k为一组,统计k中每一位数组出现的个数,个数最多的不变。
(大坑,我没有考虑如果n[1]^n[2]^n[3] != 0怎么办)

答案(错误)

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {    
        map<int,int> num_count;//存储key出现的value次
        vector<int> knums;//存储出现的最大值
        int XOR; //存储异或值
        int len = nums.size();//数组长度
        int circle = int(len/k);//有几轮重复的
        int res = len%k;//剩余的
        for(int i=0;i<k;i++){
            for(int j=0;j<=circle;j++){
                int index = j*k+i;  //nums的下标
                if(index >= len)  continue;
                num_count[nums[index]]++;
            }
            vector<int> temp;
            map<int, int>::iterator   iter;
            int max = 0;
            int flag = 0;
            for(iter = num_count.begin(); iter != num_count.end(); iter++){
                if(iter->second>max) {
                    flag = iter->first;
                    max = iter->second;
                }
            }
            knums.push_back(max) ;
            XOR = XOR^flag;
            num_count.clear();
        }
        int r = 0;
        for(int i=0;i<k;i++){
            if(XOR==0){
                r = r+ (circle - knums[i]);
            }else{
                //这里卡住了。如果异或不为0的话,还要考虑每个circle中有几个满足异或为0的。
                //我发现不能不用算法来做了。
                //大失败,开始就没考虑清楚题,以至于花了很久在调错上面,下次还是要考虑清楚。
                //去看算法吧
            }
        }
        if(res==0){
            return r;
        }else{
            return r+res;
        }
    }
};

修改

看了题解还是脱不开动态规划。没时间仔细复盘了,有空写。

class Solution {
private:
    // x 的范围为 [0, 2^10)
    static constexpr int MAXX = 1 << 10;
    // 极大值,为了防止整数溢出选择 INT_MAX / 2
    static constexpr int INFTY = INT_MAX / 2;
    
public:
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(MAXX, INFTY);
        // 边界条件 f(-1,0)=0
        f[0] = 0;
        
        for (int i = 0; i < k; ++i) {
            // 第 i 个组的哈希映射
            unordered_map<int, int> cnt;
            int size = 0;
            for (int j = i; j < n; j += k) {
                ++cnt[nums[j]];
                ++size;
            }

            // 求出 t2
            int t2min = *min_element(f.begin(), f.end());

            vector<int> g(MAXX, t2min);
            for (int mask = 0; mask < MAXX; ++mask) {
                // t1 则需要枚举 x 才能求出
                for (auto [x, countx]: cnt) {
                    g[mask] = min(g[mask], f[mask ^ x] - countx);
                }
            }
            
            // 别忘了加上 size
            for_each(g.begin(), g.end(), [&](int& val) {val += size;});
            f = move(g);
        }

        return f[0];
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/solution/shi-suo-you-qu-jian-de-yi-huo-jie-guo-we-uds2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

时间复杂度:O( 2C k + n),其中 n 是数组 nums 的长度,C 是数组 nums 中元素二进制表示的最大位数,在本题中 C = 10。对于每一个组,构造其哈希表的时间严格小于动态规划的时间,因此可以忽略不计。

空间复杂度:O(2C + n/k)动态规划需要两个长度为 2C的一维数组,每一个组 i对应的哈希表的大小为 O(n/k)

上一篇:[转] iOS (OC) 中 KVC 与 KVO 理解


下一篇:-1787. 使所有区间的异或结果为零