【LeetCode】﹝前缀树ி﹞最长单词、键值映射、最大异或值

布满荆棘的人生 2022-10-05 13:46 244阅读 0赞

【LeetCode】﹝前缀树ி﹞最长单词、键值映射、最大异或值

文章目录

    • 【LeetCode】﹝前缀树ி﹞最长单词、键值映射、最大异或值
      • 实现 Trie (前缀树)★★
      • 词典中最长的单词★
      • 键值映射★★
      • 数组中两个数的最大异或值★★
      • 与数组中元素的最大异或值★★★
      • 统计异或值在范围内的数对有多少★★★

前缀树的详细讲解和相关实现可参考往期博客高级数据结构（Ⅴ）单词查找树（Trie）

实现 Trie (前缀树)★★

208. 实现 Trie (前缀树)

【题目】Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次

【示例】

  1. 输入
  2. ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
  3. [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
  4. 输出
  5. [null, null, true, false, true, null, true]
  7. 解释
  8. Trie trie = new Trie();
  9. trie.insert("apple");
  10. trie.search("apple");   // 返回 True
  11. trie.search("app");     // 返回 False
  12. trie.startsWith("app"); // 返回 True
  13. trie.insert("app");
  14. trie.search("app");     // 返回 True

【解题思路】

  1. class Trie {
  4.     class Node{
  6.         boolean isEnd;
  7.         Node[] next;
  8.         Node () {
  10.             isEnd = false;
  11.             next = new Node[26];
  12.         }
  13.     }
  15.     Node root;
  17.     /** Initialize your data structure here. */
  18.     public Trie() {
  20.         this.root = new Node();
  21.     }
  23.     /** Inserts a word into the trie. */
  24.     public void insert(String word) {
  26.         Node p = root;
  27.         for (char c : word.toCharArray()) {
  29.             if (p.next[c - 'a'] == null) {
  31.                 p.next[c - 'a'] = new Node();
  32.             }
  33.             p = p.next[c - 'a'];
  34.         }
  35.         p.isEnd = true;
  36.     }
  38.     /** Returns if the word is in the trie. */
  39.     public boolean search(String word) {
  41.         Node p = root;
  42.         for (char c : word.toCharArray()) {
  44.             if (p.next[c - 'a'] == null) {
  46.                 return false;
  47.             } else {
  49.                 p = p.next[c - 'a'];
  50.             }
  51.         }
  52.         return p.isEnd;
  53.     }
  55.     /** Returns if there is any word in the trie that starts with the given prefix. */
  56.     public boolean startsWith(String prefix) {
  58.         Node p = root;
  59.         for (char c : prefix.toCharArray()) {
  61.             if (p.next[c - 'a'] == null) {
  63.                 return false;
  64.             } else {
  66.                 p = p.next[c - 'a'];
  67.             }
  68.         }
  69.         return true;
  70.     }
  71. }
  73. /**
  74.  * Your Trie object will be instantiated and called as such:
  75.  * Trie obj = new Trie();
  76.  * obj.insert(word);
  77.  * boolean param_2 = obj.search(word);
  78.  * boolean param_3 = obj.startsWith(prefix);
  79.  */

词典中最长的单词★

720. 词典中最长的单词

【题目】给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

若无答案，则返回空字符串。

提示：

  • 所有输入的字符串都只包含小写字母。
  • words数组长度范围为[1,1000]。
  • words[i]的长度范围为[1,30]。

【示例】

  1. 输入：
  2. words = ["w","wo","wor","worl", "world"]
  3. 输出："world"
  4. 解释： 
  5. 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

【解题思路】

方法一：排序+Set集合

  1. class Solution {
  3.     public String longestWord(String[] words) {
  5.         Set<String> set = new HashSet<>();
  6.         String res = new String();
  7.         Arrays.sort(words);
  8.         for (String str : words) {
  10.             if (str.length() == 1 || set.contains(str.substring(0, str.length() - 1))) {
  12.                 res = str.length() > res.length() ? str : res;
  13.                 set.add(str);
  14.             }
  15.         }
  16.         return res;
  17.     }
  18. }

方法二：字典树

  1. class Solution {
  3.     class Node {
  5.         boolean isEnd;
  6.         Node[] next;
  7.         String word;
  8.         Node() {
  10.             isEnd = false;
  11.             next = new Node[26];
  12.             word = null;
  13.         }
  14.     }
  16.     Node root;
  17.     String res;
  18.     int maxDepth;
  20.     public String longestWord(String[] words) {
  22.         root = new Node();
  23.         for (String word : words) {
  25.             insert(word);
  26.         }
  27.         res = "";
  28.         maxDepth = 0;
  29.         dfs(root, 0);
  30.         return res;
  31.     }
  33.     private void insert(String str) {
  35.         Node p = root;
  36.         for (char c : str.toCharArray()) {
  38.             if (p.next[c - 'a'] == null) {
  40.                 p.next[c - 'a'] = new Node();
  41.             }
  42.             p = p.next[c - 'a'];
  43.         }
  44.         p.isEnd = true;
  45.         p.word = str;
  46.     }
  48.     private void dfs(Node p, int depth) {
  50.         if (depth > 0 && !p.isEnd) {
  52.             return;
  53.         }
  54.         if (depth > maxDepth) {
  56.             maxDepth = depth;
  57.             res = p.word;
  58.         }
  59.         for (Node cur : p.next) {
  61.             if (cur != null) {
  63.                 dfs(cur, depth + 1);
  64.             }
  65.         }
  66.     }
  68. }

键值映射★★

677. 键值映射

【题目】实现一个 MapSum 类，支持两个方法，insert 和 sum：

MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

提示：

  • 1 <= key.length, prefix.length <= 50
  • key 和 prefix 仅由小写英文字母组成
  • 1 <= val <= 1000
  • 最多调用 50 次 insert 和 sum

【示例】

  1. 输入：
  2. ["MapSum", "insert", "sum", "insert", "sum"]
  3. [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
  4. 输出：
  5. [null, null, 3, null, 5]
  7. 解释：
  8. MapSum mapSum = new MapSum();
  9. mapSum.insert("apple", 3);  
  10. mapSum.sum("ap");           // return 3 (apple = 3)
  11. mapSum.insert("app", 2);    
  12. mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

【解题思路】

  1. class MapSum {
  3.     class Node{
  5.         int val;
  6.         Node[] next;
  7.         Node() {
  9.             this.val = 0;
  10.             this.next = new Node[26];
  11.         }
  12.     }
  13.     Node root;
  15.     /** Initialize your data structure here. */
  16.     public MapSum() {
  18.         root = new Node();
  19.     }
  21.     public void insert(String key, int val) {
  23.         Node p = root;
  24.         for (char c : key.toCharArray()) {
  26.             if (p.next[c - 'a'] == null) {
  28.                 p.next[c - 'a'] = new Node();
  29.             }
  30.             p = p.next[c - 'a'];
  31.         }
  32.         p.val = val;
  33.     }
  35.     public int sum(String prefix) {
  37.         Node p = root;
  38.         int sum = 0, i = 0;
  39.         while (i < prefix.length()) {
  41.             char c = prefix.charAt(i);
  42.             if (p.next[c - 'a'] == null) {
  44.                 break;
  45.             }
  46.             p = p.next[c - 'a'];
  47.             i++;
  48.         }
  49.         if (i == prefix.length()) {
  51.             sum = getSum(p);
  52.         }
  53.         return sum;
  54.     }
  56.     private int getSum(Node p) {
  58.         int cur = p.val;
  59.         for (int i = 0; i < 26; i++) {
  61.             if (p.next[i] != null) {
  63.                 cur += getSum(p.next[i]);
  64.             }
  65.         }
  66.         return cur;
  67.     }
  69. }

数组中两个数的最大异或值★★

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

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

进阶：你可以在 O(n) 的时间解决这个问题吗？

提示：

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

【示例】

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

【解题思路】

异或相同为0，不同为1，在01字典树中取二进制位不同的方向搜索，这样才能使得到的结果最大。

  • 若二进制位不同的位置字典树不为空，向此方向搜索
  • 否则，继续向相同的位置往下搜索

采取的策略是边加入边搜索，防止重复判断。

  1. class Solution {
  3.     class Node{
  5.         Node[] ns = new Node[2];
  6.     }
  7.     Node root;
  9.     private void put(int num) {
  11.         Node p = root;
  12.         for (int i = 31; i >= 0; i--) {
  14.             int t = (num >> i) & 1;
  15.             if (p.ns[t] == null) {
  17.                 p.ns[t] = new Node();
  18.             }
  19.             p = p.ns[t];
  20.         }
  21.     }
  23.     private int get(int num) {
  25.         int val = 0;
  26.         Node p = root;
  27.         for (int i = 31; i >= 0; i--) {
  29.             int a = (num >> i) & 1, b = 1 - a;
  30.             if (p.ns[b] != null) {
  32.                 val |= (b << i);
  33.                 p = p.ns[b];
  34.             } else {
  36.                 val |= (a << i);
  37.                 p = p.ns[a];
  38.             }
  39.         }
  40.         return val;
  41.     }
  43.     public int findMaximumXOR(int[] nums) {
  45.         root = new Node();
  46.         int res = 0;
  47.         for (int num : nums) {
  49.             put(num);
  50.             int t = get(num);
  51.             res = Math.max(res, num ^ t);
  52.         }
  53.         return res;
  54.     }
  55. }

与数组中元素的最大异或值★★★

1707. 与数组中元素的最大异或值

【题目】给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。

第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi) ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。

返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

提示：

  • 1 <= nums.length, queries.length <= 105
  • queries[i].length == 2
  • 0 <= nums[j], xi, mi <= 109

【示例】

  1. 输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
  2. 输出：[3,3,7]
  3. 解释：
  4. 1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
  5. 2) 1 XOR 2 = 3.
  6. 3) 5 XOR 2 = 7.

【解题思路】

离线模式查询+字典树

  1. class Solution {
  4.     private class Node{
  6.         Node[] ns = new Node[2];
  7.     }
  9.     Node root;
  11.     private void insert(int v) {
  13.         Node p = root;
  14.         for (int i = 29; i >= 0; i--) {
  16.             int t = (v >> i) & 1;
  17.             if (p.ns[t] == null) {
  19.                 p.ns[t] = new Node();
  20.             }
  21.             p = p.ns[t];
  22.         }
  23.     }
  25.     private int query(int v) {
  27.         Node p = root;
  28.         int val = 0;
  29.         for (int i = 29; i >= 0; i--) {
  31.             int t = (v >> i) & 1;
  32.             if (p.ns[t ^ 1] != null) {
  34.                 val |= 1 << i;
  35.                 t ^= 1;
  36.             }
  37.             p = p.ns[t];
  38.         }
  39.         return val;
  40.     }
  43.     public int[] maximizeXor(int[] nums, int[][] queries) {
  45.         root = new Node();
  46.         Arrays.sort(nums);
  47.         int n = queries.length;
  48.         int[][] que = new int[n][3];
  49.         for (int i = 0; i < n; i++) {
  51.             que[i][0] = queries[i][0];
  52.             que[i][1] = queries[i][1];
  53.             que[i][2] = i;
  54.         }
  55.         Arrays.sort(que, (a, b) -> {
  57.             return a[1] - b[1];
  58.         });
  60.         int[] res = new int[n];
  61.         int k = 0;
  62.         for (int[] p : que) {
  64.             while (k < nums.length && nums[k] <= p[1]) {
  66.                 insert(nums[k++]);
  67.             }
  68.             if (k == 0) {
  70.                 res[p[2]] = -1;
  71.             } else {
  73.                 res[p[2]] = query(p[0]);
  74.             }
  75.         }
  77.         return res;
  78.     }
  79. }

在线模式查询+字典树+最小值

  1. class Solution {
  3.     class Node{
  5.         int min = Integer.MAX_VALUE;
  6.         Node[] ns = new Node[2];
  7.     }
  8.     Node root;
  10.     private void insert(int x) {
  12.         Node p = root;
  13.         p.min = Math.min(p.min, x);
  14.         for (int i = 29; i >= 0; i--) {
  16.             int t = (x >> i) & 1;
  17.             if (p.ns[t] == null) {
  19.                 p.ns[t] = new Node();
  20.             }
  21.             p = p.ns[t];
  22.             p.min = Math.min(p.min, x);
  23.         }
  24.     }
  26.     private int queryMaxXor(int x, int h) {
  28.         Node p = root;
  29.         if (p.min > h) {
  31.             return -1;
  32.         }
  33.         int res = 0;
  34.         for (int i = 29; i >= 0; i--) {
  36.             int t = (x >> i) & 1;
  37.             if (p.ns[t ^ 1] != null && p.ns[t ^ 1].min <= h) {
  39.                 res |= 1 << i;
  40.                 t ^= 1;
  41.             }
  42.             p = p.ns[t];
  43.         }
  44.         return res;
  45.     }
  47.     public int[] maximizeXor(int[] nums, int[][] queries) {
  49.         root = new Node();
  50.         for (int num : nums) {
  52.             insert(num);
  53.         }
  54.         int m = queries.length;
  55.         int[] ans = new int[m];
  56.         for (int i = 0; i < m; i++) {
  58.             ans[i] = queryMaxXor(queries[i][0], queries[i][1]);
  59.         }
  60.         return ans;
  61.     }
  62. }

统计异或值在范围内的数对有多少★★★

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

【题目】给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数：low 和 high ，请返回 漂亮数对 的数目。

漂亮数对 是一个形如 (i, j) 的数对，其中 0 <= i < j < nums.length 且 low <= (nums[i] XOR nums[j]) <= high 。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= nums[i] <= 2 * 104
  • 1 <= low <= high <= 2 * 104

【示例】

  1. 输入：nums = [1,4,2,7], low = 2, high = 6
  2. 输出：6
  3. 解释：所有漂亮数对 (i, j) 列出如下：
  4.     - (0, 1): nums[0] XOR nums[1] = 5 
  5.     - (0, 2): nums[0] XOR nums[2] = 3
  6.     - (0, 3): nums[0] XOR nums[3] = 6
  7.     - (1, 2): nums[1] XOR nums[2] = 6
  8.     - (1, 3): nums[1] XOR nums[3] = 3
  9.     - (2, 3): nums[2] XOR nums[3] = 5

【解题思路】

字典树+计数

  1. class Solution {
  3.     class Node{
  5.         int count;
  6.         Node[] ns;
  7.         Node () {
  9.             count = 0;
  10.             ns = new Node[2];
  11.         }
  12.     }
  14.     Node root;
  16.     private void insert(int x) {
  18.         Node p = root;
  19.         //注意nums[i] <= 2x10^4 , 所以取最大 i << 15
  20.         for (int i = 15; i >= 0; i--) {
  22.             int t = (x >> i) & 1;
  23.             if (p.ns[t] == null) {
  25.                 p.ns[t] = new Node();
  26.             }
  27.             p = p.ns[t];
  28.             p.count += 1;
  29.         }
  30.     }
  32.     private int query(int x, int h) {
  34.         int sum = 0;
  35.         Node p = root;
  36.         for (int i = 15; i >= 0; i--) {
  38.             if (p == null) break;
  39.             int t = (x >> i) & 1;
  40.             int ht = (h >> i) & 1;
  41.             if (ht == 1) {
  43.                 //若上限h当前位为1，则与x相同的位的数异或均小于h
  44.                 if (p.ns[t] != null) {
  46.                     sum += p.ns[t].count;
  47.                 }
  48.                 //走向异或结果为1的位置
  49.                 p = p.ns[1 - t];
  50.             } else {
  52.                 //走向异或结果为0的位置
  53.                 p = p.ns[t];
  54.             }
  55.         }
  56.         return sum;
  57.     }
  59.     public int countPairs(int[] nums, int low, int high) {
  61.         root = new Node();
  62.         int res = 0;
  63.         for (int num : nums) {
  65.             res += query(num, high + 1) - query(num, low);
  66.             insert(num);
  67.         }
  68.         return res;
  69.     }
  70. }

发表评论

表情：
评论列表 （有 0 条评论，244人围观）

还没有评论，来说两句吧...

相关阅读