Medium

题目描述

给你一个整数数组 nums 和一个整数 k。

你的任务是将 nums 分割成 k 个非空子数组。对于每个子数组，计算其所有元素的按位异或值。

返回这 k 个子数组中最大异或值的最小可能值。

示例 1：

输入：nums = [1,2,3], k = 2
输出：1
解释：
最优分割是 [1] 和 [2, 3]。
- 第一个子数组的异或值是 1。
- 第二个子数组的异或值是 2 XOR 3 = 1。
子数组中的最大异或值是 1，这是最小可能值。

示例 2：

输入：nums = [2,3,3,2], k = 3
输出：2
解释：
最优分割是 [2], [3, 3], 和 [2]。
- 第一个子数组的异或值是 2。
- 第二个子数组的异或值是 3 XOR 3 = 0。
- 第三个子数组的异或值是 2。
子数组中的最大异或值是 2，这是最小可能值。

示例 3：

输入：nums = [1,1,2,3,1], k = 2
输出：0
解释：
最优分割是 [1, 1] 和 [2, 3, 1]。
- 第一个子数组的异或值是 1 XOR 1 = 0。
- 第二个子数组的异或值是 2 XOR 3 XOR 1 = 0。
子数组中的最大异或值是 0，这是最小可能值。

约束条件：

  • 1 <= nums.length <= 250
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= n

提示：

  • 使用动态规划
  • 预计算 pre[i] = nums[0] ^ … ^ nums[i-1]，这样任何子数组的异或值都是 pre[r] ^ pre[l]
  • 定义 dp[i][j] = 将前 i 个元素分割成 j 部分时可能的最小"最大异或值"
  • 对于每个 dp[i][j]，尝试所有分割点 t < i，并取 max(dp[t][j-1], pre[i] ^ pre[t]) 的最小值

解题思路

这是一道典型的动态规划题目，需要最小化分割后各子数组异或值的最大值。

核心思路：

  1. 前缀异或预处理：由于异或运算的性质，子数组 nums[l...r-1] 的异或值等于 prefix[r] ^ prefix[l]，其中 prefix[i] 表示前 i 个元素的异或值。

  2. 状态定义：dp[i][j] 表示将前 i 个元素分割成 j 个子数组时，所有子数组异或值的最大值的最小可能值。

  3. 状态转移：对于 dp[i][j]，枚举最后一个子数组的起始位置 t，则：

    • 最后一个子数组的异或值为 prefix[i] ^ prefix[t]
    • 前面 j-1 个子数组的最大异或值为 dp[t][j-1]
    • 总的最大异或值为两者的最大值

    因此：dp[i][j] = min(max(dp[t][j-1], prefix[i] ^ prefix[t])) 对所有有效的 t 取最小值。

  4. 边界条件：dp[i][1] = prefix[i]，表示前 i 个元素作为一个子数组的异或值。

  5. 优化：使用滚动数组可以优化空间复杂度，但由于数据规模较小，直接使用二维数组即可。

这种方法时间复杂度为 O(n³k)，空间复杂度为 O(nk)，对于给定约束条件是可接受的。

代码实现

class Solution {
public:
    int minXor(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefix(n + 1, 0);
        
        // 计算前缀异或
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ nums[i];
        }
        
        // dp[i][j] 表示前i个元素分成j个子数组的最小最大异或值
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
        
        // 边界条件
        dp[0][0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= min(i, k); j++) {
                if (j == 1) {
                    dp[i][j] = prefix[i];
                } else {
                    for (int t = j - 1; t < i; t++) {
                        int currentXor = prefix[i] ^ prefix[t];
                        dp[i][j] = min(dp[i][j], max(dp[t][j-1], currentXor));
                    }
                }
            }
        }
        
        return dp[n][k];
    }
};

class Solution:
    def minXor(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        
        # 计算前缀异或
        for i in range(n):
            prefix[i + 1] = prefix[i] ^ nums[i]
        
        # dp[i][j] 表示前i个元素分成j个子数组的最小最大异或值
        dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
        
        # 边界条件
        dp[0][0] = 0
        
        for i in range(1, n + 1):
            for j in range(1, min(i, k) + 1):
                if j == 1:
                    dp[i][j] = prefix[i]
                else:
                    for t in range(j - 1, i):
                        current_xor = prefix[i] ^ prefix[t]
                        dp[i][j] = min(dp[i][j], max(dp[t][j-1], current_xor))
        
        return dp[n][k]

public class Solution {
    public int MinXor(int[] nums, int k) {
        int n = nums.Length;
        int[] prefix = new int[n + 1];
        
        // 计算前缀异或
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ nums[i];
        }
        
        // dp[i][j] 表示前i个元素分成j个子数组的最小最大异或值
        int[,] dp = new int[n + 1, k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i, j] = int.MaxValue;
            }
        }
        
        // 边界条件
        dp[0, 0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= Math.Min(i, k); j++) {
                if (j == 1) {
                    dp[i, j] = prefix[i];
                } else {
                    for (int t = j - 1; t < i; t++) {
                        int currentXor = prefix[i] ^ prefix[t];
                        dp[i, j] = Math.Min(dp[i, j], Math.Max(dp[t, j-1], currentXor));
                    }
                }
            }
        }
        
        return dp[n, k];
    }
}

var minXor = function(nums, k) {
    const n = nums.length;
    const xor = new Array(n + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        xor[i + 1] = xor[i] ^ nums[i];
    }
    
    function canPartition(maxXor) {
        const dp = new Array(n + 1).fill(false);
        dp[0] = true;
        
        for (let parts = 1; parts <= k; parts++) {
            const newDp = new Array(n + 1).fill(false);
            for (let i = parts; i <= n; i++) {
                for (let j = parts - 1; j < i; j++) {
                    if (dp[j] && (xor[i] ^ xor[j]) <= maxXor) {
                        newDp[i] = true;
                        break;
                    }
                }
            }
            dp.splice(0, dp.length, ...newDp);
        }
        
        return dp[n];
    }
    
    let left = 0, right = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            right = Math.max(right, xor[j + 1] ^ xor[i]);
        }
    }
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (canPartition(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³k)三层循环：外层 O(n)，中层 O(k)，内层 O(n)
空间复杂度O(nk)二维 DP 数组的存储空间