假设我们有正整数的数组arr和查询[i] = [Li,Ri]的数组查询,对于每个查询,i都会计算从Li到Ri的元素的XOR(即arr [Li] XOR arr [ Li + 1] xor ... xor arr [Ri])。我们必须找到包含给定查询结果的数组。因此,如果输入类似于-[[1,3,4,8],而查询类似于[[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
为了解决这个问题,我们将遵循以下步骤-
n:= arr的大小
定义一个大小为n + 1的称为pre的数组,然后填充pre,使得pre [i]:= pre [i – 1] XOR arr [i – 1]
定义另一个数组
对于0到查询数量范围内的i – 1
l:=查询[i,0],r:=查询[i,1]
将l和r增加1
将pre [r] XOR pre [1-1]插入ans
返回ans
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) { int n = arr.size(); vector <int> pre(n + 1); for(int i = 1; i <=n; i++){ pre[i] = pre[i - 1] ^ arr[i - 1]; } vector <int> ans; for(int i = 0; i < queries.size(); i++){ int l = queries[i][0]; int r = queries[i][1]; l++; r++; ans.push_back(pre[r] ^ pre[l - 1]); } return ans; } }; main(){ vector<int> v = {1,3,4,8}; vector<vector<int>> v1 = {{0,1},{1,2},{0,3},{3,3}}; Solution ob; print_vector(ob.xorQueries(v, v1)); }
[1,3,4,8] [[0,1],[1,2],[0,3],[3,3]]
输出结果
[2,7,14,8]