資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢整數流中給定整數的最大異或值
在這個問題中，我們給定 Q 個查詢，每個查詢都是以下型別之一：
型別 1 - 插入 (1, i) 將值為 i 的元素新增到您的資料結構中。
型別 2 - findXOR (2, i)，查詢資料結構中所有元素與元素 i 的異或值。
資料結構最初應只包含 1 個元素，該元素為 0。
讓我們舉一個例子來理解這個問題：
輸入
Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)
輸出
15 15
解釋
Solving each query,
(1, 9) => data structure => {9}
(1, 3) => data structure => {9, 3}
(1, 7) => data structure => {9, 3, 7}
(2, 8) => maximum XOR(_, 8) = 15, XOR(7, 8)
(1, 5) => data structure => {9, 3, 7, 5}
(2, 12) => maximum XOR(_, 12) = 15, XOR(3, 12)解決方案方法
可以使用 Trie 資料結構找到問題的解決方案，Trie 資料結構是一種特殊的搜尋樹。我們將使用一個 Trie，其中每個節點有兩個子節點來儲存數字的二進位制值。之後，我們將為型別 1 的每個查詢將數字的二進位制值新增到 Trie 中。對於型別 2 的查詢，我們將找到給定值的 Trie 中的路徑，然後層級計數將給出結果。
有關 Trie 的更多資訊，請訪問 Trie 資料結構。
程式說明我們解決方案的工作原理：
示例
#include<bits/stdc++.h>
using namespace std;
struct Trie {
Trie* children[2];
bool isLeaf;
};
bool check(int N, int i) {
return (bool)(N & (1<<i));
}
Trie* newNode() {
Trie* temp = new Trie;
temp->isLeaf = false;
temp->children[0] = NULL;
temp->children[1] = NULL;
return temp;
}
void insertVal(Trie* root, int x) {
Trie* val = root;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if (! val->children[f])
val->children[f] = newNode();
val = val->children[f];
}
val->isLeaf = true;
}
int solveQueryType2(Trie *root, int x){
Trie* val = root;
int ans = 0;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if ((val->children[f ^ 1])){
ans = ans + (1 << i);
val = val->children[f ^ 1];
}
else
val = val->children[f];
}
return ans;
}
void solveQueryType1(Trie *root, int x){
insertVal(root, x);
}
int main(){
int Q = 6;
int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};
Trie* root = newNode();
for(int i = 0; i < Q; i++){
if(query[i][0] == 1 ){
solveQueryType1(root, query[i][1]);
cout<<"Value inserted to the data Structure. value =
"<<query[i][1]<<endl;
}
if(query[i][0] == 2){
cout<<"The maximum XOR with "<<query[i][1]<<" is
"<<solveQueryType2(root, query[i][1])<<endl;
}
}
return 0;
}輸出
Value inserted to the data Structure. value = 9 Value inserted to the data Structure. value = 3 Value inserted to the data Structure. value = 7 The maximum XOR with 8 is 15 Value inserted to the data Structure. value = 5 The maximum XOR with 12 is 15
更新於: 2021-03-12
124 次檢視
廣告