数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++ 子数组的异或
在这个问题中，我们给定一个数组 arr[] 和一些查询，这些查询是在数组中从 L 到 R 的范围。我们的任务是打印从 L 到 R 的子数组的异或结果。
让我们举个例子来理解这个问题：
输入 − array = {1, 4, 5, 7, 2, 9} L = 1 , R = 5
输出 −
解释 − 4^5^7^2^9
为了解决这个问题，我们将基于以下观察创建一个数组：
我们将对多个位进行异或运算，如果存在奇数个 1，则结果为 1，否则结果为 0。
现在，我们将创建一个二维数组 count 来存储 1 的个数。值 count[i][j] 是位置 i-j 的 1 的个数，也就是在子数组 arr[0..j] 中第 i 位存在的 1 的个数。所有子数组 arr[L..R] 的位的 1 的个数可以使用 count 数组找到。计算 arr[L...R] 的公式为：count[i][R] - count[i][L-1]。如果 1 的个数是奇数，则在结果中设置第 i 位。可以通过将对应于第 i 位的 2 的幂相加来获得最终结果，前提是它是设置位。
展示我们解决方案实现的程序：
示例
#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
int i, j;
for (i = 0; i < 32; i++) {
cnt[i][0] = 0;
for (j = 0; j < n; j++) {
if (j > 0) {
cnt[i][j] = cnt[i][j - 1];
}
if (arr[j] & (1 << i))
cnt[i][j]++;
}
}
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
int result = 0;
int noOfOnes;
int i, j;
for (i = 0; i < 32; i++) {
noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
if (noOfOnes & 1) {
result+=(1 << i);
}
}
return result;
}
int main(){
int arr[] = { 1, 4, 5, 7, 2, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
vector<vector<int> > count(32, vector<int>(n));
preProcessArray(arr, n, count);
int L = 1;
int R = 5;
cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
return 0;
}输出
The XOR of SubArray: 13
更新于: 2020年4月17日
97 次浏览
广告