1787. 使所有 K 个大小的段的异或为零

Hard

题目描述

给你一个数组 nums 和一个整数 k。段 [left, right]（其中 left <= right）的异或结果是所有下标在 left 和 right 之间的元素的异或结果：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] < 2^10

注意：

要使所有长度为 K 的段的异或结果都为零，nums[i] 必须等于 nums[i+k]
基本上，我们需要使前 K 个元素的异或结果为 0，然后修改它们。

解题思路

这个问题的关键洞察是：如果所有长度为 k 的段的异或都为零，那么对于任意位置 i，必须有 nums[i] == nums[i+k]。这意味着数组具有周期性，周期长度为 k。

因此，问题转化为：

将数组按位置模 k 分组，每组内所有元素必须相等
这 k 个组的代表元素的异或必须为 0

我们使用动态规划来解决：

dp[i][xor] 表示处理前 i 个组，当前异或值为 xor 时的最小修改次数
对于第 i 组，我们可以选择保持某个已有值（只需修改其他位置），或者选择一个全新的值（修改整组）

具体步骤：

将数组按位置模 k 分组，统计每组中各值的出现次数
使用 DP 计算最优方案：对于每组，枚举可能的取值
最终答案是 dp[k][0]，表示 k 组处理完且异或为 0 的最小修改次数

时间复杂度主要由状态数和转移决定，空间复杂度为状态存储。

代码实现

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int n = nums.size();
        int maxXor = 1024; // 2^10
        
        // 按位置 % k 分组
        vector<unordered_map<int, int>> groups(k);
        vector<int> groupSize(k);
        
        for (int i = 0; i < n; i++) {
            groups[i % k][nums[i]]++;
            groupSize[i % k]++;
        }
        
        // dp[i][xor] = 处理前i个组，当前异或值为xor的最小修改次数
        vector<vector<int>> dp(k + 1, vector<int>(maxXor, INT_MAX));
        dp[0][0] = 0;
        
        for (int i = 0; i < k; i++) {
            vector<int> minCost(maxXor, INT_MAX);
            int globalMin = INT_MAX;
            
            // 找到上一轮的最小值
            for (int xor = 0; xor < maxXor; xor++) {
                if (dp[i][xor] != INT_MAX) {
                    globalMin = min(globalMin, dp[i][xor]);
                }
            }
            
            for (int xor = 0; xor < maxXor; xor++) {
                if (dp[i][xor] == INT_MAX) continue;
                
                // 选择组i中已存在的值
                for (auto& [val, cnt] : groups[i]) {
                    int newXor = xor ^ val;
                    int cost = dp[i][xor] + (groupSize[i] - cnt);
                    dp[i + 1][newXor] = min(dp[i + 1][newXor], cost);
                }
                
                // 选择组i中不存在的值（修改整组）
                for (int val = 0; val < maxXor; val++) {
                    if (groups[i].count(val)) continue;
                    int newXor = xor ^ val;
                    int cost = dp[i][xor] + groupSize[i];
                    dp[i + 1][newXor] = min(dp[i + 1][newXor], cost);
                }
            }
        }
        
        return dp[k][0];
    }
};

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        
        n = len(nums)
        max_xor = 1024  # 2^10
        
        # 按位置 % k 分组
        groups = [defaultdict(int) for _ in range(k)]
        group_size = [0] * k
        
        for i, num in enumerate(nums):
            groups[i % k][num] += 1
            group_size[i % k] += 1
        
        # dp[i][xor] = 处理前i个组，当前异或值为xor的最小修改次数
        dp = [[float('inf')] * max_xor for _ in range(k + 1)]
        dp[0][0] = 0
        
        for i in range(k):
            for xor in range(max_xor):
                if dp[i][xor] == float('inf'):
                    continue
                
                # 选择组i中已存在的值
                for val, cnt in groups[i].items():
                    new_xor = xor ^ val
                    cost = dp[i][xor] + (group_size[i] - cnt)
                    dp[i + 1][new_xor] = min(dp[i + 1][new_xor], cost)
                
                # 选择组i中不存在的值（修改整组）
                for val in range(max_xor):
                    if val in groups[i]:
                        continue
                    new_xor = xor ^ val
                    cost = dp[i][xor] + group_size[i]
                    dp[i + 1][new_xor] = min(dp[i + 1][new_xor], cost)
        
        return dp[k][0]

public class Solution {
    public int MinChanges(int[] nums, int k) {
        int n = nums.Length;
        int maxXor = 1024; // 2^10
        
        // 按位置 % k 分组
        var groups = new Dictionary<int, int>[k];
        var groupSize = new int[k];
        
        for (int i = 0; i < k; i++) {
            groups[i] = new Dictionary<int, int>();
        }
        
        for (int i = 0; i < n; i++) {
            int group = i % k;
            if (!groups[group].ContainsKey(nums[i])) {
                groups[group][nums[i]] = 0;
            }
            groups[group][nums[i]]++;
            groupSize[group]++;
        }
        
        // dp[i][xor] = 处理前i个组，当前异或值为xor的最小修改次数
        var dp = new int[k + 1, maxXor];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < maxXor; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 0; i < k; i++) {
            for (int xor = 0; xor < maxXor; xor++) {
                if (dp[i, xor] == int.MaxValue) continue;
                
                // 选择组i中已存在的值
                foreach (var pair in groups[i]) {
                    int val = pair.Key;
                    int cnt = pair.Value;
                    int newXor = xor ^ val;
                    int cost = dp[i, xor] + (groupSize[i] - cnt);
                    dp[i + 1, newXor] = Math.Min(dp[i + 1, newXor], cost);
                }
                
                // 选择组i中不存在的值（修改整组）
                for (int val = 0; val < maxXor; val++) {
                    if (groups[i].ContainsKey(val)) continue;
                    int newXor = xor ^ val;
                    int cost = dp[i, xor] + groupSize[i];
                    dp[i + 1, newXor] = Math.Min(dp[i + 1, newXor], cost);
                }
            }
        }
        
        return dp[k, 0];
    }
}

var minChanges = function(nums, k) {
    const n = nums.length;
    const maxVal = 1024; // 2^10
    
    // Group elements by position modulo k
    const groups = Array(k).fill().map(() => new Map());
    for (let i = 0; i < n; i++) {
        const group = i % k;
        groups[group].set(nums[i], (groups[group].get(nums[i]) || 0) + 1);
    }
    
    // dp[i][xor] = minimum changes for first i groups with XOR = xor
    let dp = new Map();
    dp.set(0, 0);
    
    for (let i = 0; i < k; i++) {
        const newDp = new Map();
        const groupSize = Math.ceil((n - i) / k);
        
        // Option 1: Keep some existing value in this group
        for (const [val, count] of groups[i]) {
            for (const [prevXor, prevCost] of dp) {
                const newXor = prevXor ^ val;
                const newCost = prevCost + (groupSize - count);
                if (!newDp.has(newXor) || newDp.get(newXor) > newCost) {
                    newDp.set(newXor, newCost);
                }
            }
        }
        
        // Option 2: Change all elements in this group to a new value
        const minPrevCost = Math.min(...dp.values());
        for (let val = 0; val < maxVal; val++) {
            for (const [prevXor, prevCost] of dp) {
                const newXor = prevXor ^ val;
                const newCost = prevCost + groupSize;
                if (!newDp.has(newXor) || newDp.get(newXor) > newCost) {
                    newDp.set(newXor, newCost);
                }
            }
        }
        
        dp = newDp;
    }
    
    return dp.get(0) || Infinity;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(k × 1024²)
空间复杂度	O(k × 1024)

其中 k 是给定参数，1024 是可能的异或值范围（2^10）。时间复杂度主要由 DP 状态转移决定，每个状态需要枚举所有可能的值。空间复杂度主要用于存储 DP 状态。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目