資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告