資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢與給定陣列範圍異或和最大的數字
要解決一個問題，其中給定一個數組和一些查詢。現在在每個查詢中，給定一個範圍。現在我們需要找到一個數字，使得它與 x 的異或和最大化，例如
Input : A = {20, 11, 18, 2, 13}
Three queries as (L, R) pairs
1 3
3 5
2 4
Output : 2147483629
2147483645
2147483645在這個問題中，我們將對每個位置上數字中存在的 1 進行字首計數，現在我們已經預先計算了 1 的數量，因此為了找到給定範圍 L 到 R 中 1 的數量，我們需要用預先計算到 R 的數量減去預先計算到 L 的數量。
查詢解決方案的方法
在這種方法中，因為我們需要找到最大和，所以我們需要使異或的大多數位等於 1；因此，我們檢查對於任何位，如果 1 的數量大於 0 的數量，那麼我們將 x 的該位置重置為 0，因為現在大多數數字的該位等於 1，所以當我們將這些大多數的 1 與 0 配對時，最終我們將使該位的大多數等於 1，因此這就是我們最大化答案的方法。
示例
上述方法的 C++ 程式碼
#include <bits/stdc++.h>
using namespace std;
#define MAX 2147483647 // 2^31 - 1
int prefix[100001][32]; // the prefix array
void prefix_bit(int A[], int n){ // taking prefix count of 1's present
for (int j = 0; j < 32; j++) // we keep 0th count as 0 and our prefix array starts with index 1
prefix[0][j] = 0;
for (int i = 1; i <= n; i++){ // making our prefix array
int a = A[i - 1]; // ith element
for (int j = 0; j < 32; j++){ // as our number is less than 2^32 so we traverse for bit 0 to 31
int x = 1 << j; // traversing in bits
if (a & x) // if this bit is one so we make the prefix count as prevcount + 1
prefix[i][j] = 1 + prefix[i - 1][j];
else
prefix[i][j] = prefix[i - 1][j];
}
}
}
int maximum_num(int l, int r){
int numberofbits = r - l + 1; // the number of elements in the range hence the number of bits
int X = MAX; // we take the max value such that all of it's bits are one
// Iterating over each bit
for (int i = 0; i < 31; i++){
int x = prefix[r][i] - prefix[l - 1][i]; // calculating the number of set bits in the given range
if (x >= numberofbits - x){ // is number of 1's is more than number of 0's
int currentbit = 1 << i; // we set the current bit to prefix for toggling that bit in x
X = X ^ currentbit; // we make toggle that bit from 1 to 0
}
}
return X; // answer
}
int main(){
int n = 5, q = 3; // number of element in our array and number of queries present
int A[] = { 210, 11, 48, 22, 133 }; // elements in our array
int L[] = { 1, 4, 2 }, R[] = { 3, 14, 4 }; // given queries
prefix_bit(A, n); // creating prefix bit array
for (int i = 0; i < q; i++)
cout << maximum_num(L[i], R[i]) << "\n";
return 0;
}輸出
2147483629 2147483647 2147483629
上述程式碼的解釋
在這種方法中，我們首先計算每一位存在的 1 的字首計數。現在，當我們得到這個計數時，我們就解決了我們最大的問題，即遍歷查詢。從現在開始，我們將不會遍歷每個範圍。因此，我們可以透過我們的字首陣列來計算。我們的主要邏輯是，當我們遇到一個 1 的數量大於 0 的數量的位置時，我們計算該範圍內重置位和設定位的數量。因此，我們現在在 x 中重置該位，因為我們已將 x 初始化為 2^31 - 1，所以它的所有位都將被設定，並且我們透過切換 x 中的位來找到我們的答案。
結論
在本教程中，我們解決了一個問題，即查詢與給定陣列範圍異或和最大的數字。我們還學習了此問題的 C++ 程式以及我們解決此問題的完整方法（常規）。我們可以用其他語言（如 C、Java、Python 和其他語言）編寫相同的程式。我們希望您覺得本教程有所幫助。
更新於： 2021 年 11 月 25 日
214 次檢視
廣告