Hard

题目描述

给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每个查询，你必须找到 nums[li..ri] 的任何子数组的最大异或分数。

数组 a 的异或分数通过在 a 上重复应用以下操作直到只剩一个元素来计算，该元素就是分数：

  • 同时将 a[i] 替换为 a[i] XOR a[i + 1]，对所有索引 i（除了最后一个）执行此操作。
  • 移除 a 的最后一个元素。

返回一个大小为 q 的数组 answer，其中 answer[i] 是查询 i 的答案。

示例 1：

输入：nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

输出：[12,60,60]

解释：

在第一个查询中，nums[0..2] 有 6 个子数组 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或分数分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，是所有异或分数中最大的。

在第二个查询中，nums[1..4] 中异或分数最大的子数组是 nums[1..4]，分数为 60。

在第三个查询中，nums[0..5] 中异或分数最大的子数组是 nums[1..4]，分数为 60。

示例 2：

输入：nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

输出：[7,14,11,14,5]

约束：

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 2^31 - 1
  • 1 <= q == queries.length <= 10^5
  • queries[i].length == 2
  • queries[i] = [li, ri]
  • 0 <= li <= ri <= n - 1

解题思路

这道题的关键在于理解异或分数的计算过程和发现其中的规律。

思路分析：

  1. 异或分数的本质：给定数组 [a, b, c]，异或分数的计算过程是：

    • 第一轮：[a⊕b, b⊕c]
    • 第二轮：[(a⊕b)⊕(b⊕c)] = [a⊕c]
    • 最终得到 a⊕c

  2. 动态规划递推关系：设 dp[i][j] 表示子数组 nums[i..j] 的异或分数。根据题目提示，我们可以发现：

    • dp[i][j] = dp[i][j-1] ⊕ dp[i+1][j]
    • 基础情况：dp[i][i] = nums[i]

  3. 预计算所有子数组的异或分数：使用动态规划计算出所有可能子数组的异或分数，存储在二维数组中。

  4. 预计算最大值：为了快速回答查询，我们还需要预计算每个区间内所有子数组异或分数的最大值。设 maxXor[i][j] 表示在区间 [i,j] 内所有子数组的最大异或分数。

  5. 回答查询：对于每个查询 [l,r]，直接返回 maxXor[l][r]。

这种方法的优势是预处理后可以 O(1) 回答每个查询，适合查询数量很大的场景。

代码实现

class Solution {
public:
    vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        vector<vector<int>> maxXor(n, vector<int>(n, 0));
        
        // 初始化对角线
        for (int i = 0; i < n; i++) {
            dp[i][i] = nums[i];
            maxXor[i][i] = nums[i];
        }
        
        // 计算所有子数组的异或分数
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = dp[i][j-1] ^ dp[i+1][j];
            }
        }
        
        // 计算每个区间的最大异或分数
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                maxXor[i][j] = max({dp[i][j], maxXor[i][j-1], maxXor[i+1][j]});
            }
        }
        
        // 回答查询
        vector<int> result;
        for (auto& query : queries) {
            result.push_back(maxXor[query[0]][query[1]]);
        }
        
        return result;
    }
};

class Solution:
    def maximumSubarrayXor(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        dp = [[0] * n for _ in range(n)]
        max_xor = [[0] * n for _ in range(n)]
        
        # 初始化对角线
        for i in range(n):
            dp[i][i] = nums[i]
            max_xor[i][i] = nums[i]
        
        # 计算所有子数组的异或分数
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = dp[i][j-1] ^ dp[i+1][j]
        
        # 计算每个区间的最大异或分数
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                max_xor[i][j] = max(dp[i][j], max_xor[i][j-1], max_xor[i+1][j])
        
        # 回答查询
        result = []
        for l, r in queries:
            result.append(max_xor[l][r])
        
        return result

public class Solution {
    public int[] MaximumSubarrayXor(int[] nums, int[][] queries) {
        int n = nums.Length;
        int[,] dp = new int[n, n];
        int[,] maxXor = new int[n, n];
        
        // 初始化对角线
        for (int i = 0; i < n; i++) {
            dp[i, i] = nums[i];
            maxXor[i, i] = nums[i];
        }
        
        // 计算所有子数组的异或分数
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i, j] = dp[i, j - 1] ^ dp[i + 1, j];
            }
        }
        
        // 计算每个区间的最大异或分数
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                maxXor[i, j] = Math.Max(dp[i, j], Math.Max(maxXor[i, j - 1], maxXor[i + 1, j]));
            }
        }
        
        // 回答查询
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            result[i] = maxXor[queries[i][0], queries[i][1]];
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number[]}
 */
var maximumSubarrayXor = function(nums, queries) {
    const n = nums.length;
    const dp = Array(n).fill().map(() => Array(n).fill(0));
    const maxXor = Array(n).fill().map(() => Array(n).fill(0));
    
    // 初始化对角线
    for (let i = 0; i < n; i++) {
        dp[i][i] = nums[i];
        maxXor[i][i] = nums[i];
    }
    
    // 计算所有子数组的异或分数
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            dp[i][j] = dp[i][j - 1] ^ dp[i + 1][j];
        }
    }
    
    // 计算每个区间的最大异或分数
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            maxXor[i][j] = Math.max(dp[i][j], maxXor[i][j - 1], maxXor[i + 1][j]);
        }
    }
    
    // 回答查询
    const result = [];
    for (const [l, r] of queries) {
        result.push(maxXor[l][r]);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)预处理需要计算所有子数组的异或分数和最大值，每个查询 O(1)
空间复杂度O(n²)需要两个 n×n 的二维数组存储 dp 和 maxXor

相关题目