数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告