C ++中子数组的XOR查询

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有正整数的数组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

例子（C ++）

让我们看下面的实现以更好地理解-

#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]

以上是 C ++中子数组的XOR查询 的全部内容， 来源链接： utcz.com/z/361625.html

回到顶部