【Day29】1787.使所有区间的异或结果为零

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

给你一个整数数组 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]

提示:

  • 1 <= k <= nums.length <= 2000

  • 0 <= nums[i] < 210

    题解:

第一种情况采用贪心的方法求得最优解。因为修改后的元素可能是原序列中没有出现过的元素。如果修改的某一列的元素是原序列中没有出现过的元素,那么这种情况下一定可以用贪心的办法求出最优解,做法是将众数最小的一列中的每个数变成一个全新的,该列中没有出现的,使得每个周期内的元素的异或和为0的数。

第二种情况采用dp的方法求得最优解在这种情况下,由于没有最终修改后的元素是原数组中存在的数,因此可以从前往后枚举每一列,然后枚举选择第几行的数作为这列元素修改后的元素,由于异或具有交换性质,因此不具有顺序的问题,所以可以采用dp的方法递推出将序列变成数组中本来存在的某个数的情况。边界,f[0] [0] = 0,目标状态是f[k] [0],状态表示f[i] [j]为前i列异或和为j的情况下的最小值。

class Solution {
public:
    // 1.某一列用了一个全新的数
    // 2.每一列用了原来的数

    const int N = 1024, INF = 1e8;
    int s[1024]; // 求众数
    int minChanges(vector& nums, int k) {
        int n = nums.size(), m = (n + k - 1) / k;
        vector> f(k + 1, vector(N, INF));
        int cnt = 0, minv = INF; // 每一列代价
        // f[i][j] 第i列的异或和为j
        f[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            int len = m;
            memset(s, 0 , sizeof s);
            if (n % k && n % k < i) len--;
            for (int j = 0; j < len; j ++) {
                s[nums[j * k + i - 1]]++;
            }
            int maxv = 0;
            for (int j = 0; j < N; j++) {
                maxv = max(maxv, s[j]);
            }
            cnt += len - maxv;
            minv = min(minv, maxv); // 众数最少的那一列  不用众数  而用全新的数

            for (int j = 0; j < N; j++) { // 异或和为j
                for (int u = 0; u < len; u++) { // 每一行
                    int x = nums[u * k + i - 1], cost = len - s[x];
                    f[i][j] = min(f[i][j], f[i - 1][j ^ x] + cost);
                }
            }
        }
        // cnt: 每一列的代价
        // minv表示 某一列不用众数时的代价 si - maxv -> si 变成全新的数代价
        return min(cnt + minv, f[k][0]);
    }
};

   转载规则


《【Day29】1787.使所有区间的异或结果为零》 Tyzhao 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【Day30】1190.反转每对括号间的子串 【Day30】1190.反转每对括号间的子串
1190. 反转每对括号间的子串给出一个字符串 s(仅含有小写英文字母和括号)。 请你按照从括号内到外的顺序,逐层反转每对匹配括号中的字符串,并返回最终的结果。 注意,您的结果中 不应 包含任何括号。 示例 1: 输入:s = "
2021-05-26
下一篇 
【Day28】664.奇怪的打印机 【Day28】664.奇怪的打印机
664. 奇怪的打印机有台奇怪的打印机有以下两个特殊要求: 打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符,并且会覆盖掉原来已有的字符。 给你一个字符串 s ,你的任务是计算这个打印机打印它需要的
2021-05-24
  目录