Medium

题目描述

给你一个长度为 n 的整数数组 nums 和一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri, ki, vi]。

对于每个查询，你必须按顺序执行以下操作：

  • 设置 idx = li
  • 当 idx <= ri 时：
    • 更新：nums[idx] = (nums[idx] * vi) % (10^9 + 7)
    • 设置 idx += ki

返回处理完所有查询后 nums 中所有元素的按位异或。

示例 1：

输入：nums = [1,1,1], queries = [[0,2,1,4]]
输出：4
解释：
单个查询 [0, 2, 1, 4] 将索引 0 到索引 2 的每个元素乘以 4。
数组从 [1, 1, 1] 变为 [4, 4, 4]。
所有元素的异或为 4 ^ 4 ^ 4 = 4。

示例 2：

输入：nums = [2,3,1,5,4], queries = [[1,4,2,3],[0,2,1,2]]
输出：31
解释：
第一个查询 [1, 4, 2, 3] 将索引 1 和 3 处的元素乘以 3，数组变为 [2, 9, 1, 15, 4]。
第二个查询 [0, 2, 1, 2] 将索引 0、1 和 2 处的元素乘以 2，结果为 [4, 18, 2, 15, 4]。
最终，所有元素的异或为 4 ^ 18 ^ 2 ^ 15 ^ 4 = 31。

约束条件：

  • 1 <= n == nums.length <= 10³
  • 1 <= nums[i] <= 10⁹
  • 1 <= q == queries.length <= 10³
  • queries[i] = [li, ri, ki, vi]
  • 0 <= li <= ri < n
  • 1 <= ki <= n
  • 1 <= vi <= 10⁵

解题思路

这道题要求我们按照给定的查询规则修改数组，然后计算所有元素的异或值。

解题思路：

由于题目提示使用暴力解法，而且数据规模较小（n ≤ 1000，q ≤ 1000），我们可以直接模拟整个过程：

  1. 处理每个查询：对于每个查询 [li, ri, ki, vi]，从索引 li 开始，每次跳跃 ki 个位置，直到超过 ri
  2. 范围内乘法操作：对于每个符合条件的索引，将该位置的值乘以 vi 并对 10^9 + 7 取模
  3. 计算最终异或值：处理完所有查询后，对整个数组进行异或运算

实现细节：

  • 使用 while 循环来处理每个查询中的索引更新
  • 注意取模操作防止整数溢出
  • 最后遍历数组计算异或结果

时间复杂度主要取决于所有查询涉及的总索引数量。在最坏情况下，每个查询可能涉及 O(n) 个索引，总体复杂度为 O(q × n)。

这种直接模拟的方法在给定的数据规模下是完全可行的，代码实现也比较直观易懂。

代码实现

class Solution {
public:
    int xorAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
        const int MOD = 1e9 + 7;
        
        for (auto& query : queries) {
            int l = query[0], r = query[1], k = query[2], v = query[3];
            for (int idx = l; idx <= r; idx += k) {
                nums[idx] = (1LL * nums[idx] * v) % MOD;
            }
        }
        
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        
        return result;
    }
};

class Solution:
    def xorAfterQueries(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        for l, r, k, v in queries:
            idx = l
            while idx <= r:
                nums[idx] = (nums[idx] * v) % MOD
                idx += k
        
        result = 0
        for num in nums:
            result ^= num
        
        return result

public class Solution {
    public int XorAfterQueries(int[] nums, int[][] queries) {
        const int MOD = 1000000007;
        
        foreach (var query in queries) {
            int l = query[0], r = query[1], k = query[2], v = query[3];
            for (int idx = l; idx <= r; idx += k) {
                nums[idx] = (int)((long)nums[idx] * v % MOD);
            }
        }
        
        int result = 0;
        foreach (int num in nums) {
            result ^= num;
        }
        
        return result;
    }
}

var xorAfterQueries = function(nums, queries) {
    const MOD = 1e9 + 7;
    
    for (const [l, r, k, v] of queries) {
        for (let idx = l; idx <= r; idx += k) {
            nums[idx] = (nums[idx] * v) % MOD;
        }
    }
    
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(q × n)，其中 q 是查询数量，n 是数组长度。最坏情况下每个查询需要处理 O(n) 个元素
空间复杂度O(1)，只使用常数额外空间，原地修改数组