算法字符串

01Trie

字数统计: 753字   |   阅读时长: 3分
, , ,

摘要: 01Trie 的实现，附代码模板和应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 Trie 中我们了解了 Trie 的原理与实现。如果 Trie 的节点只含有 0, 1 这两种值，将数的二进制视为字符串，则可以用 Trie 维护数字，此时的 Trie 称为 01Trie。

本文我们首先给出 01Trie 的代码模板，然后解决力扣上最经典的相关问题 421. 数组中两个数的最大异或值。

01Trie

01Trie就是对数的二进制位建Trie树,经常用来处理一些和异或有关的问题。

01Trie的建树(插入)，搜索过程与 Trie 基本一样(Ref: Trie)。有一些差别：

  • 01Trie 的节点只有两个子节点 left,right。
  • 插入的数字均视为长为 32 的 01 串，相当于单词都是定长的。
  • 0 对应 left, 1 对应 right。

代码模板 (C++)

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
struct Trie01Node
{
    Trie01Node *left, *right;
    Trie01Node()
    {
        left = nullptr, right = nullptr;
    }
    ~Trie01Node(){}
};

class Trie01
{
public:
    Trie01()
    {
        root = new Trie01Node();
    }

    ~Trie01()
    {
        if(root)
        {
            delete_subtree(root);
        }
    }

    void insert(int num)
    {
        Trie01Node *iter = root;
        // 从高位到低位枚举
        for(int i = 30; i >= 0; --i)
        {
            if((num >> i) & 1)
            {
                if(!iter -> right)
                    iter -> right = new Trie01Node();
                iter = iter -> right;
            }
            else
            {
                if(!iter -> left)
                    iter -> left = new Trie01Node();
                iter = iter -> left;
            }
        }
    }

    int search(int x)
    {
        Trie01Node *iter = root;
        /*
         * 给定 x，找到使得 x ^ a 最大的 a
         * 尽可能让高位上的 x 与 a 不同
         * 所有的数都是长度 30 捅到底的
         */
        int a = 0;
        for(int i = 30; i >= 0; --i)
        {
            if((x >> i) & 1)
            {
                if(iter -> left)
                    iter = iter -> left;
                else
                {
                    iter = iter -> right;
                    a |= (1 << i);
                }
            }
            else
            {
                if(iter -> right)
                {
                    iter = iter -> right;
                    a |= (1 << i);
                }
                else
                    iter = iter -> left;
            }
        }
        return a ^ x;
    }

private:
    Trie01Node *root;

    void delete_subtree(Trie01Node* node)
    {
        if(node -> left)
            delete_subtree(node -> left);
        if(node -> right)
            delete_subtree(node -> right);
        delete node;
        node = nullptr;
    }
};

题目

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

示例 1：
输入：nums = [3,10,5,25,2,8]
输出：28
解释：最大运算结果是 5 XOR 25 = 28.

示例 2：
输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
输出：127

提示：

1
2
1 <= nums.length <= 2 * 1e5
0 <= nums[i] <= 231 - 1

算法：贪心、01Trie

1
2
3
// ai ^ aj
// 给定 ai，找到使得 ai ^ aj 最大的 aj
// 尽可能让 ai 与 aj 在高位上不同

以上是一种贪心思想，01Trie 就是支持这种贪心思想的数据结构。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        Trie01 *trie01 = new Trie01();
        for(int num: nums)
            trie01 -> insert(num);
        int result = 0;
        for(int num: nums)
            result = max(result, trie01 -> search(num));
        return result;
    }
};
Share