字典树
CPU爆炸
理论基础
- Trie 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。
- 其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。
- 应用：
。在纯算法领域，前缀树算是一种较为常用的数据结构。
。不过如果在工程中，不考虑前缀匹配的话，基本上使用 hash 就能满足。如果考虑前缀匹配的话，工程也不会使用 Trie 。一方面是字符集大小不好确定，另外，对于个别的超长字符 Trie 会进一步变深。
- 模板：添加字符串至字典树，查询时返回次数
。二维数组
- 使用二维数组 trie[]来存储我们所有的单词字符。
- 使用 index 来自增记录我们到底用了多少个格子（相当于给被用到格子进行编号）。
- 使用 count[]数组记录某个格子被「被标记为结尾的次数」（当 idx 编号的格子被标记了 n 次，则有 count[idx]=n）。
class Trie { int N = 100009; // N为节点个数，直接设置为十万级 int[][] trie; int[] count; int index; public Trie() { trie = new int[N][26]; count = new int[N]; index = 0; } public void insert(String s) {// 将字符串str添加进字典树 int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) trie[p][u] = ++index;// 创建结点并赋予编号index p = trie[p][u];// 走到下一个结点 } count[p]++;// 计数 } public int search(String s) {// 返回当前字符串出现的次数 int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) return false;//若当前结点不存在，那么直接返回0 p = trie[p][u]; } return count[p]; } }
- 复杂度
- 时间复杂度：O(len)，len为入参字符串长度
- 空间复杂度：O(nk)，n为节点数量，k为字符集大小
。动态扩点
建立 TrieNode 结构节点。
class Trie { class TrieNode { int cnt; TrieNode[] tns = new TrieNode[26]; } TrieNode root; public Trie() { root = new TrieNode(); } public void insert(String s) { TrieNode p = root; for(int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (p.tns[u] == null) p.tns[u] = new TrieNode();//创建结点 p = p.tns[u]; } p.cnt++; } public int search(String s) { TrieNode p = root; for(int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (p.tns[u] == null) return 0; p = p.tns[u]; } return p.cnt; } }
- 复杂度
- 时间复杂度：O(len)，len为入参字符串长度
- 空间复杂度：O(nk)，n 为节点数量，k为字符集大小
。静态数组
减小空间复杂度，并避免垃圾回收
class Trie { // 以下 static 成员独一份，被创建的多个 Trie 共用 static int N = 100009; // 直接设置为十万级 static int[][] trie = new int[N][26]; static int[] count = new int[N]; static int index = 0; // 在构造方法中完成重置 static 成员数组的操作 // 这样做的目的是为减少 new 操作（无论有多少测试数据，上述 static 成员只会被 new 一次） public Trie() { for (int row = index; row >= 0; row--) { Arrays.fill(trie[row], 0); } Arrays.fill(count, 0); index = 0; } public void insert(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) trie[p][u] = ++index; p = trie[p][u]; } count[p]++; } public int search(String s) { int p = 0; for (int i = 0; i < s.length(); i++) { int u = s.charAt(i) - 'a'; if (trie[p][u] == 0) return 0; p = trie[p][u]; } return count[p]; } }
- 复杂度
- 时间复杂度：O(len)，len为入参字符串长度
- 空间复杂度：O(nk)，n为节点数量，k 为字符集大小
相关题目
统计异或值在范围内的数对有多少【LC1803】
Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.
A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.
字典树
- 思路：
。首先使用字典树存储数组中元素的二进制形式，由于nums[i]≤2∗10 4 ，因此用15位二进制就可以表示；
。由容斥原理可得，异或值在[low,high]之间的对数=异或值为high的对数-异或值为low−1的对数
。然后求出nums[i]异或nums[0,i−1]小于等于target的数量，再将nums[i]加入字典树中
具体步骤：从高位开始枚举，符合则计数，不符合直接return
- 如果target的第j 位为1，那么与之前数字第j 位异或结果可以为1也可以为0
- 如果target的第j位为1，那么与之前数字第j 位异或结果只能为0
- 二维数组实现
class Solution { int[][] trie; int[] cnt; int idx; public int countPairs(int[] nums, int low, int high) { trie = new int[nums.length * 16][2]; cnt = new int[nums.length * 16]; return get(nums, high) - get(nums, low - 1); } int get(int[] nums, int high) { idx = 0; for (int i = 0; i < trie.length; i++) trie[i][0] = trie[i][1] = cnt[i] = 0; int ans = 0; for (int i = 0; i < nums.length; i++) { ans += query(nums[i], high); add(nums[i]); } return ans; } void add(int x) { int p = 0; for (int i = 14; i >= 0; i--) { int u = (x >> i) & 1; if (trie[p][u] == 0) trie[p][u] = ++idx; p = trie[p][u]; //移动到下一个结点 cnt[p]++; // 个数增加，cnt[x]代表x结点出现的次数 } } int query(int x, int high) { int sum = 0, p = 0; for (int i = 14; i >= 0; i--) { int u = (x >> i) & 1; if (((high >> i) & 1) == 1) { //high当前i位为1, 那么x与以前数当前i位的异或可以位1或者0 sum += cnt[trie[p][u]];//加上与x异或后当前i位为0的数量 if (trie[p][u ^ 1] == 0) return sum; //没有结点可以继续走下去，直接返回 p = trie[p][u ^ 1]; //继续往异或的结点走下去 } else { //high当前i位为0, x与以前数异或的第i为必须为0 if (trie[p][u] == 0) return sum; //没有结点走下去 p = trie[p][u]; //寻找与x的第i位相同的进制，异或结果为0 } } sum += cnt[p]; //加上走到最后的结点数 return sum; } } 作者：Tizzi 链接：https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/solutions/2045650/javac-zi-dian-shu-fu-zi-dian-shu-mo-ban-566um/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(nlogC)
- 空间复杂度：O(nlogC)，n为节点数量，C为字符集大小
- TrieNode
class Solution { class TrieNode{ TrieNode[] next = new TrieNode[2]; int cnt; } TrieNode root; public int countPairs(int[] nums, int low, int high) { return get(nums, high) - get(nums, low - 1); } public int get(int[] nums, int t){ root = new TrieNode(); int ans = 0; for (int i = 0; i < nums.length; i++){ ans += search(nums[i], t); add(nums[i]); } return ans; } public void add(int num){ TrieNode p = root; for (int i = 14; i >= 0; i--){ // 高位至低位 int u = (num >> i) & 1; if (p.next[u] == null) p.next[u] = new TrieNode(); p = p.next[u]; p.cnt++; } } public int search(int num, int t){ int count = 0; TrieNode p = root; for (int i = 14; i >= 0; i--){ int u = (num >> i) & 1; if (((t >> i) & 1) == 1){// t的第i位为1 if (p.next[u] != null) count += p.next[u].cnt;// 结果为0 之后节点为任意值均符合条件 直接加cnt if (p.next[u ^ 1] == null) return count;// 之后没有节点可以走了 直接返回结果 p = p.next[u ^ 1];// t的第i位为0 }else{ if (p.next[u] == null) return count; p = p.next[u]; } } count += p.cnt; return count; } }
。复杂度
- 时间复杂度：O(nlogC)
- 空间复杂度：O(nlogC)，n 为节点数量，C为字符集大小
*哈希表
- 思路：
。基于异或性质x⊕y=t等价于$y = t \oplus x $，可以统计nums中每个数的出现次数，并记录在哈希表cnt中
。然后遍历cnt的每一个键x ，那么cnt[x]∗cnt[x⊕t]，累加结果除以2即为数组中任意两数异或结果为y 的对数
。那么对区间[low,high]的每个数都这样统计即可得最终结果。
- 实现[超时]
class Solution { public int countPairs(int[] nums, int low, int high) { Map<Integer, Integer> numToCount = new HashMap<>(); for (int num : nums){ numToCount.put(num, numToCount.getOrDefault(num, 0) + 1); } int count = 0; for (int i = low; i <= high; i++){ for (var node: numToCount.entrySet()){ count += node.getValue() * numToCount.getOrDefault(node.getKey() ^ i,0); } } return count / 2; } }
。复杂度
- 时间复杂度O(n∗C)，n为数组长度，C为high−low
- 空间复杂度：O(n)
- 优化：
。将[0,t]分成若干区间，计算每个区间的答案[没咋懂]
- 若右数第m位(注意m>1)是1, 则可划分出一组只需考虑第m位及以左;
- 特别地, 若右边从第1位开始连续m位是1, 则有一组, 只需考虑第m+1位及以左. (例如若 x=10011, 最后一组忽略右2位) 统一来看, 则可通过 x+1 的 第m位(m>=1)为条件进行判断, 计算异或时记得减一
。基于容斥原理，把[low,high]转化为计算[0,high]和[0,low−1]相减的结果
class Solution { public int countPairs(int[] nums, int low, int high) { int ans = 0; var cnt = new HashMap<Integer, Integer>(); for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1); for (++high; high > 0; high >>= 1, low >>= 1) { var nxt = new HashMap<Integer, Integer>(); for (var e : cnt.entrySet()) { int x = e.getKey(), c = e.getValue(); if ((high & 1) == 1) ans += c * cnt.getOrDefault(x ^ (high - 1), 0); if ((low & 1) == 1) ans -= c * cnt.getOrDefault(x ^ (low - 1), 0); nxt.put(x >> 1, nxt.getOrDefault(x >> 1, 0) + c); } cnt = nxt; } return ans / 2; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/solutions/2045560/bu-hui-zi-dian-shu-zhi-yong-ha-xi-biao-y-p2pu/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度
- 时间复杂度：O(n)，严格来说为O ( n + n l o g U /n ) ,n 为数组长度，U 为数组中的最大值
- 空间复杂度：O ( n )
