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） 的应用，结合了 贪心算法。字典树主要用于处理按位的前缀问题，本题通过位运算来处理异或操作，在此基础上使用字典树来动态地处理插入、删除和查询操作。

解题思路

1. 字典树（Trie）基础：
   • 字典树是一种树形数据结构，其中每个节点代表一个“位”，从根节点到叶节点的路径代表一个数字。
   • 本题中我们采用 32 位整数（假设是 32 位的整型）来表示数字，从最高位到最低位逐位插入字典树。
2. 操作的类型：
   • 插入操作（op = 1）：将一个数字插入到字典树中。
   • 删除操作（op = 2）：从字典树中删除一个数字。对于删除操作，我们可以通过减少相应节点的计数来实现。
   • 查询操作（op = 3）：查询一个给定数字与字典树中的某个数字的异或值的最大值。为了实现这个查询，我们从根节点出发，按位选择与当前数字异或后最大的数字。
3. 最大异或值的求解：
   • 对于每一个查询操作，我们从字典树的根节点开始，依次处理每一位，贪心地选择异或值较大的路径。
   • 假设当前数字的第 i 位为 x，我们优先选择与 x 相反的位来最大化异或值。
   • 通过递归的方式，从根节点到叶节点选择最佳路径。
4. 删除操作的实现：
   • 删除操作不完全是简单的从字典树中移除某个数字，而是通过减少该数字对应的路径上节点的计数。如果某条路径的节点计数为 0，才会真正删除该路径。

代码大致描述

代码实现的核心是通过字典树来实现动态的插入、删除和查询。具体实现步骤如下：

1. TrieNode 类：
   • children[0] 和 children[1] 存储指向左右子节点的指针。
   • count[0] 和 count[1] 存储左右子节点出现的次数（用于删除操作）。
2. TireTree 类：
   • insert(int num)：将数字插入字典树，从根节点开始，逐位插入。
   • remove(int num)：删除字典树中的数字，逐位减少节点计数。
   • findMaxXOR(int num)：查询给定数字与字典树中的数字的最大异或值，采用贪心算法选择异或值较大的路径。
   • empty()：检查字典树是否为空。
3. 主函数：
   • 处理输入，依次执行每个操作。如果是插入操作，则调用 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)。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏