跳到主要内容

异或题库

子数组异或查询​

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [Li, Ri]。

对于每个查询 i，请你计算从 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例1:

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8] 
解释：
数组中元素的二进制表示形式是：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

示例2:

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

方案 前缀异或​

思路:

  1. 计算前缀异或数组xors
  2. 计算每个查询的结果: 第i个查询的结果为:xors[queries[i][0]]^xors[queries[i][1]+1]
function xorQueries(arr, queries) {
    const len=arr.length;
    const xors=new Array(len+1).fill(0);
    for(let i=0;i<len;i++){
        xors[i+1]=xors[i]^arr[i];
    }
    const lenQ=queries.length;
    const result=new Array(lenQ).fill(0);
    for(let i=0;i<lenQ;i++){
        result[i]=xors[queries[i][0]]^xors[queries[i][1]+1];
    }
    return result;
};

性能分析:

  • 时间复杂度: O(len+lenQ)
  • 空间复杂度: O(len)

形成两个异或相等数组的三元组数目​

给你一个整数数组 arr 。

现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。

a 和 b 定义如下：

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]

  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

注意：^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

示例1:

输入：arr = [2,3,1,6,7]
输出：4
解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)

示例2:

输入：arr = [1,1,1,1,1]
输出：10

方案 前缀疑惑与哈希表​

思路:

  • 设sums[i]表示长度为n的数组nums的异或前缀和，则有方程:

    • sums[i]=0 (i=0)

    • sums[i]=nums[0]^nums[1]^……^nums[i-1] (1<=i<=n)

  • 由上可得出，sums[i]与sums[i-1]的关系为

    • sums[i]=0 (i=0)

    • sums[i]=sums[i-1]+nums[i-1] (1<=i<=n)

  • 设数组nums的子区间[i,j]的元素异或和可表示为sums[i]^sums[j+1],所以由题可知a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]、b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

    • a=sums[i]^sums[j]

    • b=sums[j]^sums[k+1]

  • 如果a=b，则有sums[i]^sums[j]=sums[j]^sums[k+1],即sums[i]=sums[k+1]

  • 遍历下标i，当满足sums[i]=sums[k+1]时

    • 记录下标i的出现次数

    • 记录下标i之和

function countTriplets(arr) {
    const len=arr.length;
    const sums=[0];
    for(let item of arr){
        sums.push(sums[sums.length-1]^item);
    }
    const cnt=new Map();
    const total=new Map();
    let result=0;
    for(let i=0;i<len;i++){
        if(cnt.has(sums[i+1])){
            result+=cnt.get(sums[i+1])*i-total.get(sums[i+1])
        }
        cnt.set(sums[i],(cnt.get(sums[i]) || 0) + 1);
        total.set(sums[i],(total.get(sums[i]) || 0) + i);
    }
    return result;
};

性能分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)