算法笔记-字典树/前缀树

image.png

字典树型

  1. 定义字典树结构

    1
    2
    3
    4
    class Tire {
        Tire[] Next = new Tire[2];
        int Cnt;
    }

  2. 构造字典树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    private void add(int num) {
        Tire cur = root;
        for (int i = 0; i < 32; i++) {
            int bit = (num>>i) & 1;
            if (cur.Next[bit] == null) cur.Next[bit] = new Tire();
            cur.Next[bit].Cnt++;
            cur = cur.Next[bit];
        }
    }

  3. 查询字典树

    1
    2
    3
    4
    5
    6
    7
    8
    private int query(int[] bits, int cnt) {
        Tire cur = root;
        for (int i = 0; i <= cnt && i < 32; i++) {
            if (cur.Next[bits[i]] == null) return 0;
            cur = cur.Next[bits[i]];
        }
        return cur.Cnt;
    }

相关题目

1803. 统计异或值在范围内的数对有多少（hard）

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class Solution {
    class Tire {
        Tire[] Next = new Tire[2];
        int Cnt;
    }

    int ret;
    Tire root = new Tire();

    public int countPairs(int[] nums, int low, int high) {
        int n = nums.length;
        int[] lowBit = bit(low);
        int[] highBit = bit(high);
        for (int i = n - 1; i >= 0; i--) {
            int[] bits = bit(nums[i]);
            //计算nums[j]前缀
            countPairs(lowBit, highBit, bits);
            //插入tire树中
            add(bits);
        }
        return ret;
    }
    //确认限制
    // 0 <= i < j < nums.length
    // low <= (nums[i] XOR nums[j]) <= high
    // nums[i] XOR nums[j]
    // XOR 相同为0,不同为1

    // 通过与low和high比较来确定nums[j]
    // 10101001 low
    // 10110101 nums[i]
    // 11001010 high

    // 存在的情况
    // 1.low和high该位都是1,那nums[i] XOR nums[j]必须是1,那nums[j]取决于nums[i]的该位取反
    // 2.low和high该位都是0,那nums[i] XOR nums[j]必须是0,那nums[j]取决于nums[i]的该位相同
    // 3.low=1和high=0（首位不可能出现这种情况）,需要根据前面的来确定

    // 4.low=0和high=1,那nums[j]该位可以是1或0
    // 4.1 如果该位取0,那后续的位取值必须大于等于lowBit,无需再考虑highBit
    // 4.2 如果该位取1,那后续的位取值必须小于等于highBit,无需再考虑lowBit

    // 10110101 nums[j]...

    // 从后向前遍历数组，查找能和当前nums[i] XOR 满足条件的个数
    private void countPairs(int[] lowBit, int[] highBit, int[] bits) {
        int[] qbs1 = new int[32];
        int[] qbs2 = new int[32];
        int i = 0;
        for (; i < 32; i++) {
            if (lowBit[i] == 1 && highBit[i] == 1) qbs1[i] = qbs2 [i] = bits[i] ^ 1;//情况1
            if (lowBit[i] == 0 && highBit[i] == 0) qbs1[i] = qbs2 [i] = bits[i]; //情况2
            // 情况4
            if (lowBit[i] == 0 && highBit[i] == 1) {
                qbs1[i] = bits[i];//bits[i] ^ x = 0
                qbs2[i] = bits[i] ^ 1;//bits[i] ^ x = 1
                //4.1
                int idx = i + 1;
                for (; idx < 32; idx++) {
                    if (lowBit[idx] == 1) qbs1[idx] = bits[idx] ^ 1;
                    if (lowBit[idx] == 0) {
                        qbs1[idx] = bits[idx] ^ 1;
                        ret += query(qbs1, idx);
                        qbs1[idx] = bits[idx];
                    }
                }
                ret += query(qbs1, idx);
                //4.2
                idx = i + 1;
                for (; idx < 32; idx++) {
                    if (highBit[idx] == 0) qbs2[idx] = bits[idx];
                    if (highBit[idx] == 1) {
                        qbs2[idx] = bits[idx];
                        ret += query(qbs2, idx);
                        qbs2[idx] = bits[idx] ^ 1;
                    }
                }
                ret += query(qbs2, idx);
                return;
            }
        }
        ret += query(qbs1, i);
    }

    private int query(int[] bits, int cnt) {
        Tire cur = root;
        for (int i = 0; i <= cnt && i < 32; i++) {
            if (cur.Next[bits[i]] == null) return 0;
            cur = cur.Next[bits[i]];
        }
        return cur.Cnt;
    }

    private void add(int[] bits) {
        Tire cur = root;
        for (int i = 0; i < 32; i++) {
            if (cur.Next[bits[i]] == null) cur.Next[bits[i]] = new Tire();
            cur.Next[bits[i]].Cnt++;
            cur = cur.Next[bits[i]];
        }
    }

    // 获取
    private int[] bit(int n) {
        int[] ret = new int[32];
        int i = 31;
        for (; i >= 0; i--) {
            ret[i] = n & 1;
            n >>= 1;
        }
        return ret;
    }

}

208. 实现 Trie (前缀树)（mid）

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
class Trie {

    // 构造Trie树节点
    class TrieNode {

        // 标识该节点是否是字符串的结束节点
        boolean isEnd = false;
        // 当前节点的孩子节点
        TrieNode[] next = new TrieNode[26];

        // 设置当前节点为一个字符串的结束节点
        public void setIsEnd (boolean isEnd) {
            this.isEnd = isEnd;
        }

    }

    // root为根节点
    TrieNode root;

    /** Initialize your data structure here. */
    public Trie()  {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        
        char[] chs = word.toCharArray();
        // 表示从根节点开始向下构建
        TrieNode node = root;
        for (int i = 0; i < chs.length; i++) {
            
            int u = chs[i] - 'a';
            // 判断node的子节点集合中是否已经存在了chs[i], 不存在则创建
            if (node.next[u] == null) 
                node.next[u] = new TrieNode();
            // 继续向下构建
            node = node.next[u];
        
        }

        // 当前TrieNode节点是一个字符串的结尾
        node.setIsEnd(true);

    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        
        char[] chs = word.toCharArray();
        // 表示从根节点开始向下构建
        TrieNode node = root;
        for (int i = 0; i < chs.length; i++) {
            
            int u = chs[i] - 'a';
            // 判断node的子节点集合中是否已经存在了chs[i], 不存在则创建
            if (node.next[u] == null) 
                return false;
            // 继续向下构建
            node = node.next[u];
        
        }

        // 当前TrieNode节点是否一个字符串的结尾
        return node.isEnd;

    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {

        char[] chs = prefix.toCharArray();
        // 表示从根节点开始向下构建
        TrieNode node = root;
        for (int i = 0; i < chs.length; i++) {
            
            int u = chs[i] - 'a';
            // 判断node的子节点集合中是否已经存在了chs[i], 不存在则创建
            if (node.next[u] == null) 
                return false;
            // 继续向下构建
            node = node.next[u];
        
        }

        // 前缀查找成功
        return true;

    }
}

相关资料

基础算法 > 刷题记录
算法笔记-字典树/前缀树
https://mikeygithub.github.io/2019/12/26/yuque/算法笔记-字典树!前缀树/
作者
Mikey
发布于
2019年12月26日
许可协议