T3.最大异或值 - 饿了么
题目描述
小柒最近想到了一个好玩的游戏,这个游戏一共会进行n轮,每一轮,小柒会从下方三种操作中选择一种进行:
-
在黑板上写一个整数x;
-
擦去黑板上的一个整数x(此操作之前保证黑板上有这个整数);
-
询问黑板上哪个数字与整数x的异或值最大(若黑板上此时没有数字,则输出 -1)。
对于每一次询问操作,你需要告诉他答案。
输入描述
第一行输入一个正整数 n(1 ≤ n ≤ 2*10^5) 代表操作的轮数。 此后几行,每行先输入一个整数op(1 ≤ op ≤ 3)代表操作类型,编号同题干; 随后在同一行输入一个整数 x(1<=x<=10^9)代表操作的参数。 除此之外,保证存在至少一次询问操作。
输出描述
对于每一次询问操作,输出一个整数,代表答案。
示例1
输入:
10
1 5
1 7
1 4
3 8
2 4
1 2
1 6
3 9
2 6
3 9
输出:
15
15
14
C++
#include <bits/stdc++.h>
using namespace std;
// 定义字典树节点
class TrieNode {
public:
TrieNode() {
children[0] = children[1] = nullptr; // 初始化左右子节点为空
count[0] = count[1] = 0; // 初始化左右子节点的计数为 0
}
// 0,1 子节点
TrieNode *children[2]{}; // children[0] 对应值为 0 的子节点,children[1] 对应值为 1 的子节点
int count[2]{}; // 记录每个子节点的出现次数,方便删除操作
};
// 字典树类
class TireTree {
private:
TrieNode *root; // 字典树的根节点
// 更新字典树(插入或删除一个数字)
void update(TrieNode *node, int num, int bitPos, int d) {
if (bitPos < 0) return; // 当 bitPos 小于 0 时,表示已经遍历完所有的位
int bit = (num >> bitPos) & 1; // 获取当前数字在 bitPos 位置上的值(0 或 1)
// 如果子节点为空,创建新的子节点
if (!node->children[bit]) {
node->children[bit] = new TrieNode();
}
node->count[bit] += d; // 更新当前位对应子节点的计数,d 为插入时 +1,删除时 -1
update(node->children[bit], num, bitPos - 1, d); // 递归处理下一个位
}
public:
// 构造函数,初始化字典树
TireTree() {
root = new TrieNode();
}
// 判断字典树是否为空
bool empty() {
return root->count[0] + root->count[1] == 0; // 如果左右子节点计数都为 0,表示树为空
}
// 插入一个数字 num 到字典树中
void insert(int num) {
update(root, num, 31, 1); // 假设数字为 32 位,最高位为 31
}
// 从字典树中删除一个数字 num
void remove(int num) {
update(root, num, 31, -1); // 删除时更新计数为 -1
}
// 查找与给定数字 num 异或结果最大的数字
int findMaxXOR(int num) {
TrieNode *node = root; // 从根节点开始查找
int ans = 0; // 存储当前最大异或值
// 假设数字为 32 位,从最高位开始遍历
for (int bitPos = 31; bitPos >= 0; bitPos--) {
int bit = (num >> bitPos) & 1; // 获取当前数字在 bitPos 位上的值
int toggledBit = 1 - bit; // 取反当前位的值(如果当前位是 0,则希望找到 1,反之亦然)
// 如果当前位的反转位的子节点存在,优先选择反转位的子节点
if (node->count[toggledBit] > 0) {
ans += (toggledBit << bitPos); // 将该位加入到最大异或值中
node = node->children[toggledBit]; // 进入对应的子树继续查找
} else {
ans += (bit << bitPos); // 如果反转位子节点不存在,则选择当前位
node = node->children[bit]; // 进入对应的子树继续查找
}
}
return ans; // 返回找到的最大异或值
}
// 析构函数,释放字典树内存
~TireTree() {
deleteTrie(root);
}
// 递归删除字典树的节点
void deleteTrie(TrieNode *node) {
if (!node) return; // 如果节点为空,直接返回
deleteTrie(node->children[0]); // 递归删除左子树
deleteTrie(node->children[1]); // 递归删除右子树
delete node; // 删除当前节点
}
};
int main() {
int n, op, x; // n 表示操作次数,op 表示操作类型,x 表示数字
cin >> n; // 读取操作次数
TireTree tire; // 创建字典树对象
for (int i = 0; i < n; i++) {
cin >> op >> x; // 读取操作类型和数字 x
if (op == 1) {
tire.insert(x); // 如果是插入操作,调用 insert() 方法
} else if (op == 2) {
tire.remove(x); // 如果是删除操作,调用 remove() 方法
} else {
if (tire.empty()) {
cout << -1 << endl; // 如果字典树为空,输出 -1
} else {
cout << tire.findMaxXOR(x) << endl; // 查询最大异或值并输出
}
}
}
return 0; // 程序结束
}
题目分析
这道题目是一个典型的“字典树”(Trie)应用题,结合了 位运算 和 字典树 的操作,主要目的是通过多次查询、插入、删除操作来求解给定整数与字典树中的数的异或值的最大值。可以通过字典树来高效地进行异或操作的查询。
题目类型
这道题目属于 字典树(Trie) 的应用,结合了 贪心算法。字典树主要用于处理按位的前缀问题,本题通过位运算来处理异或操作,在此基础上使用字典树来动态地处理插入、删除和查询操作。
解题思路
- 字典树(Trie)基础:
- 字典树是一种树形数据结构,其中每个节点代表一个“位”,从根节点到叶节点的路径代表一个数字。
- 本题中我们采用 32 位整数(假设是 32 位的整型)来表示数字,从最高位到最低位逐位插入字典树。
- 操作的类型:
- 插入操作(op = 1):将一个数字插入到字典树中。
- 删除操作(op = 2):从字典树中删除一个数字。对于删除操作,我们可以通过减少相应节点的计数来实现。
- 查询操作(op = 3):查询一个给定数字与字典树中的某个数字的异或值的最大值。为了实现这个查询,我们从根节点出发,按位选择与当前数字异或后最大的数字。
- 最大异或值的求解:
- 对于每一个查询操作,我们从字典树的根节点开始,依次处理每一位,贪心地选择异或值较大的路径。
- 假设当前数字的第 i 位为
x
,我们优先选择与x
相反的位来最大化异或值。- 通过递归的方式,从根节点到叶节点选择最佳路径。
- 删除操作的实现:
- 删除操作不完全是简单的从字典树中移除某个数字,而是通过减少该数字对应的路径上节点的计数。如果某条路径的节点计数为 0,才会真正删除该路径。
代码大致描述
代码实现的核心是通过字典树来实现动态的插入、删除和查询。具体实现步骤如下:
- TrieNode 类:
children[0]
和children[1]
存储指向左右子节点的指针。count[0]
和count[1]
存储左右子节点出现的次数(用于删除操作)。- TireTree 类:
insert(int num)
:将数字插入字典树,从根节点开始,逐位插入。remove(int num)
:删除字典树中的数字,逐位减少节点计数。findMaxXOR(int num)
:查询给定数字与字典树中的数字的最大异或值,采用贪心算法选择异或值较大的路径。empty()
:检查字典树是否为空。- 主函数:
- 处理输入,依次执行每个操作。如果是插入操作,则调用
insert()
;如果是删除操作,则调用remove()
;如果是查询操作,则调用findMaxXOR()
并输出结果。时间复杂度分析
- 每次插入和删除操作的时间复杂度是 O(32),即与数字的位数相关,最多进行 32 次操作(对于 32 位整数)。
- 每次查询操作的时间复杂度也是 O(32),需要遍历数字的每一位。
- 因为一共进行 n 次操作(n ≤ 2 * 10^5),所以总体的时间复杂度是 O(n * 32),即 O(n)。
空间复杂度分析
- 字典树的空间复杂度主要取决于插入的数字的数量。每个数字需要 32 个节点(每个节点存储一个位的信息)。所以,空间复杂度是 O(n * 32),即 O(n)。
#面经##春招##校招##C++##笔试#整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏