0%

子数组异或查询

题目

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

对于每个查询 i,请你计算从Li RiXOR 值(即 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]
解释:
[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]

思路

  • 由于 a ^ 0 = a, a ^ b ^ a = b
  • 我们可以得到在区间 [i, j]上的异或
1
2
3
4
5
6
7
8
9
10
xors[j + 1] = (arr[0] ^ arr[1] ^ ... ^ arr[j]);
xors[i] = (arr[0] ^ arr[1] ^ ... ^ arr[i - 1]);
arr[i] ^ arr[i + 1] ... ^ arr[j] = s[i] ^ s[j + 1];

// 比如[1, 3];
arr[1] ^ arr[2] ^ arr[3];
xors[4] = arr[0] ^ arr[1] ^ arr[2] ^ arr[3];
xors[1] = arr[0];

arr[1] ^ arr[2] ^ arr[3] = xors[4] ^ xors[1];

步骤

  1. 建立xors数组保存arr前n项异或
  2. 遍历queries数组,获取所求区间[i, j]
  3. 求值 xors[i] ^ xors[j + 1],添加到返回的数组中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param {number[]} arr
* @param {number[][]} queries
* @return {number[]}
*/
var xorQueries = function (arr, queries) {
let arrLength = arr.length;
let xors = new Array().fill(0);

// 添加arr的前i个异或到xors的第i + 1个中
for (let i = 0; i < arrLength; i++){
xors[i + 1] = xors[i] ^ arr[i];
}

let result = [];
queries.forEach(value => {
// [i, j]区间异或
result.push(xors[value[0]] ^ xors[value[1] + 1])
});

return result;
};

Vim-实用技巧

大小写

命令 用途
g~ 反转大小写
gU 转换为大写
gu 转换为小写
guu 转换当前行小写
gUU 转换当前行为大写
阅读全文 »

JavaScript-位运算符

位运算符处理 32 位数。

该运算中的任何数值运算数都会被转换为 32 位的数, 然后进行运算,最后转换回 JavaScript 数。

阅读全文 »