Leetcode 421. 数组中两个数的最大异或值

(Updated: )
(3 mins to read)

题意

求数组num中任意两个数异或的最大值。

做法

显然可以用01字典树。

Leetcode题一般不需要考虑delete问题，这种题还是定义一个全局的数据结构和一个全局的内存池比较方便。

但是Leetcode有一个坑是所有测例是在一份代码里一起运行的，因此还需要考虑清空问题，当时发现全局零初始化的nxt数组的值非零，debug了好久才意识到是这个原因，还以为是什么奇奇怪怪的未定义行为。

还有一点是字典树的大小应该是N * BIT_NUM的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int N = 7e6 + 5;

int tot;
struct Node {
    Node* nxt[2];
    static Node* newNode();
    void insert(int v, int b) {
        int x = (v >> b) & 1;
        if (!nxt[x]) nxt[x] = Node::newNode();
        if (b) nxt[x]->insert(v, b - 1); 
    }
    int ask(int v, int b) {
        if (b < 0) return 0;
        int x = (v >> b) & 1;
        if (nxt[!x]) {
            return (1 << b) | nxt[!x]->ask(v, b - 1);
        } else if (nxt[x]) {
            return nxt[x]->ask(v, b - 1);
        } else {
            return 0;
        }
    }
} nodes[N];

Node* Node::newNode() {
    return nodes + (++tot);
}

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Node* root = nodes;
        int ans = 0;
        for (int num : nums) {
            ans = max(ans, root->ask(num, 30));
            root->insert(num, 30);
        }
        for (int i = 0; i <= tot; i++) {
            nodes[i].nxt[0] = nodes[i].nxt[1] = nullptr;
        }
        tot = 0;
        return ans;
    }
};

这题还有更简单的做法，从高位往低位枚举，忽略低位，然后看当前位能不能取1（用unordered_set检查即可），其实和二分差不多。