【leetcode】【剑指offer Ⅱ】067. 最大的异或

问题描述：

• 给定一个整数数组 nums，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n。

核心思路：

• 前缀树经典应用题。
• 想象一棵 01 前缀树，就可以把一个数值以二进制形式存入前缀树中。
  • 而所谓的异或结果最大，其实就是要求异或操作中的两个数值在二进制表示上有越多的不同就越好。
  • 所以最重要的是要将数值从高位向低位访问保存进前缀树中。【不能从低位向高位的顺序来保存】
  • 将 nums 数组中所有数保存进前缀树后，再重新访问 nums 中所有数值，假设当前数值为 nums[i]，则从高位向低位访问 nums[i]，假若当前位为 1，则优先向另一方向访问，也就是说当前位位 1 则优先取 0，假若位 0 不能访问，则访问位 1。
  • 简单来说，对于 nums[i] 而言，可以从其二进制表示中的最高位开始往低位找，尽量让每一位的异或结果为 1，这样找到的异或结果才是最大的。
• 该题考察了前缀和 + 贪心，贪心策略体现在从高到低贪心匹配更高位。
  • 该题一定要从高位向低位访问，不能从低位向高位访问，因为高位差异越大越好。

代码实现：

class Trie
{
public:
    vector<Trie*> next;
    Trie(): next(2, nullptr) {}
    void insert(int num)
    {
        Trie* cur = this;
        for(int i = 31; i >= 0; --i)
        {
            int idx = (num >> i) & 1;
            if(!cur->next[idx]) cur->next[idx] = new Trie();
            cur = cur->next[idx];
        }
        return;
    }
    
    int searchXOR(int num)
    {
        int tmp = num;
        Trie* cur = this;
        int ans = 0;
        for(int i = 31; i >= 0; --i)
        {
            int idx = (num >> i) & 1;
            int ridx = 1-idx; // 另一方向
            if(cur->next[ridx]) // 优先向另一方向走
            {
                ans += (1 << i);
                cur = cur->next[ridx];
            }
            else
                cur = cur->next[idx];
        }
        return ans;
    }
};

class Solution
{
private:
    Trie* root;
public:
    int findMaximumXOR(vector<int>& nums)
    {
        root = new Trie();
        for(int num : nums) root->insert(num);
        int ans = 0;
        for(int num : nums) ans = max(ans, root->searchXOR(num));
        return ans;
    }
};
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
45
46
47
48
49
50
51
52