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

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

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

### 文章目录 ###

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

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

### 实现 Trie (前缀树)★★ ###

[208. 实现 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` 次

【**示例**】

输入
    ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
    [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
    输出
    [null, null, true, false, true, null, true]
    
    解释
    Trie trie = new Trie();
    trie.insert("apple");
    trie.search("apple");   // 返回 True
    trie.search("app");     // 返回 False
    trie.startsWith("app"); // 返回 True
    trie.insert("app");
    trie.search("app");     // 返回 True

【**解题思路**】

class Trie {
        
    
        class Node{
        
            boolean isEnd;
            Node[] next;
            Node () {
        
                isEnd = false;
                next = new Node[26];
            }
        }
    
        Node root;
    
        /** Initialize your data structure here. */
        public Trie() {
        
            this.root = new Node();
        }
        
        /** Inserts a word into the trie. */
        public void insert(String word) {
        
            Node p = root;
            for (char c : word.toCharArray()) {
        
                if (p.next[c - 'a'] == null) {
        
                    p.next[c - 'a'] = new Node();
                }
                p = p.next[c - 'a'];
            }
            p.isEnd = true;
        }
        
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
        
            Node p = root;
            for (char c : word.toCharArray()) {
        
                if (p.next[c - 'a'] == null) {
        
                    return false;
                } else {
        
                    p = p.next[c - 'a'];
                }
            }
            return p.isEnd;
        }
        
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
        
            Node p = root;
            for (char c : prefix.toCharArray()) {
        
                if (p.next[c - 'a'] == null) {
        
                    return false;
                } else {
        
                    p = p.next[c - 'a'];
                }
            }
            return true;
        }
    }
    
    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */

--------------------

### 词典中最长的单词★ ###

[720. 词典中最长的单词][720.]

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

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

**提示：**

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

【**示例**】

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

【**解题思路**】

方法一：排序+Set集合

class Solution {
        
        public String longestWord(String[] words) {
        
            Set<String> set = new HashSet<>();
            String res = new String();
            Arrays.sort(words);
            for (String str : words) {
        
                if (str.length() == 1 || set.contains(str.substring(0, str.length() - 1))) {
        
                    res = str.length() > res.length() ? str : res;
                    set.add(str);
                }
            }
            return res;
        }
    }

方法二：字典树

class Solution {
        
        class Node {
        
            boolean isEnd;
            Node[] next;
            String word;
            Node() {
        
                isEnd = false;
                next = new Node[26];
                word = null;
            }
        }
    
        Node root;
        String res;
        int maxDepth;
    
        public String longestWord(String[] words) {
        
            root = new Node();
            for (String word : words) {
        
                insert(word);
            }
            res = "";
            maxDepth = 0;
            dfs(root, 0);
            return res;
        }
    
        private void insert(String str) {
        
            Node p = root;
            for (char c : str.toCharArray()) {
        
                if (p.next[c - 'a'] == null) {
        
                    p.next[c - 'a'] = new Node();
                }
                p = p.next[c - 'a'];
            }
            p.isEnd = true;
            p.word = str;
        }
    
        private void dfs(Node p, int depth) {
        
            if (depth > 0 && !p.isEnd) {
        
                return;
            }
            if (depth > maxDepth) {
        
                maxDepth = depth;
                res = p.word;
            }
            for (Node cur : p.next) {
        
                if (cur != null) {
        
                    dfs(cur, depth + 1);
                }
            }
        }
    
    }

--------------------

### 键值映射★★ ###

[677. 键值映射][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`

【**示例**】

输入：
    ["MapSum", "insert", "sum", "insert", "sum"]
    [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
    输出：
    [null, null, 3, null, 5]
    
    解释：
    MapSum mapSum = new MapSum();
    mapSum.insert("apple", 3);  
    mapSum.sum("ap");           // return 3 (apple = 3)
    mapSum.insert("app", 2);    
    mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

【**解题思路**】

class MapSum {
        
        class Node{
        
            int val;
            Node[] next;
            Node() {
        
                this.val = 0;
                this.next = new Node[26];
            }
        }
        Node root;
    
        /** Initialize your data structure here. */
        public MapSum() {
        
            root = new Node();
        }
        
        public void insert(String key, int val) {
        
            Node p = root;
            for (char c : key.toCharArray()) {
        
                if (p.next[c - 'a'] == null) {
        
                    p.next[c - 'a'] = new Node();
                }
                p = p.next[c - 'a'];
            }
            p.val = val;
        }
        
        public int sum(String prefix) {
        
            Node p = root;
            int sum = 0, i = 0;
            while (i < prefix.length()) {
        
                char c = prefix.charAt(i);
                if (p.next[c - 'a'] == null) {
        
                    break;
                }
                p = p.next[c - 'a'];
                i++;
            }
            if (i == prefix.length()) {
        
                sum = getSum(p);
            }
            return sum;
        }
    
        private int getSum(Node p) {
        
            int cur = p.val;
            for (int i = 0; i < 26; i++) {
        
                if (p.next[i] != null) {
        
                    cur += getSum(p.next[i]);
                }
            }
            return cur;
        }
    
    }

--------------------

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

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

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

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

**提示：**

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

【**示例**】

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

【**解题思路**】

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

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

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

class Solution {
        
        class Node{
        
            Node[] ns = new Node[2];
        }
        Node root;
    
        private void put(int num) {
        
            Node p = root;
            for (int i = 31; i >= 0; i--) {
        
                int t = (num >> i) & 1;
                if (p.ns[t] == null) {
        
                    p.ns[t] = new Node();
                }
                p = p.ns[t];
            }
        }
    
        private int get(int num) {
        
            int val = 0;
            Node p = root;
            for (int i = 31; i >= 0; i--) {
        
                int a = (num >> i) & 1, b = 1 - a;
                if (p.ns[b] != null) {
        
                    val |= (b << i);
                    p = p.ns[b];
                } else {
        
                    val |= (a << i);
                    p = p.ns[a];
                }
            }
            return val;
        }
    
        public int findMaximumXOR(int[] nums) {
        
            root = new Node();
            int res = 0;
            for (int num : nums) {
        
                put(num);
                int t = get(num);
                res = Math.max(res, num ^ t);
            }
            return res;
        }
    }

--------------------

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

[1707. 与数组中元素的最大异或值][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`

【**示例**】

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

【**解题思路**】

离线模式查询+字典树

class Solution {
        
    
        private class Node{
        
            Node[] ns = new Node[2];
        }
    
        Node root;
    
        private void insert(int v) {
        
            Node p = root;
            for (int i = 29; i >= 0; i--) {
        
                int t = (v >> i) & 1;
                if (p.ns[t] == null) {
        
                    p.ns[t] = new Node();
                }
                p = p.ns[t];
            }
        }
    
        private int query(int v) {
        
            Node p = root;
            int val = 0;
            for (int i = 29; i >= 0; i--) {
        
                int t = (v >> i) & 1;
                if (p.ns[t ^ 1] != null) {
        
                    val |= 1 << i;
                    t ^= 1;
                }
                p = p.ns[t];
            }
            return val;
        }
    
    
        public int[] maximizeXor(int[] nums, int[][] queries) {
        
            root = new Node();
            Arrays.sort(nums);
            int n = queries.length;
            int[][] que = new int[n][3];
            for (int i = 0; i < n; i++) {
        
                que[i][0] = queries[i][0];
                que[i][1] = queries[i][1];
                que[i][2] = i;
            }
            Arrays.sort(que, (a, b) -> {
        
                return a[1] - b[1];
            });
    
            int[] res = new int[n];
            int k = 0;
            for (int[] p : que) {
        
                while (k < nums.length && nums[k] <= p[1]) {
        
                    insert(nums[k++]);
                }
                if (k == 0) {
        
                    res[p[2]] = -1;
                } else {
        
                    res[p[2]] = query(p[0]);
                }
            }
    
            return res;
        }
    }

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

class Solution {
        
        class Node{
        
            int min = Integer.MAX_VALUE;
            Node[] ns = new Node[2];
        }
        Node root;
    
        private void insert(int x) {
        
            Node p = root;
            p.min = Math.min(p.min, x);
            for (int i = 29; i >= 0; i--) {
        
                int t = (x >> i) & 1;
                if (p.ns[t] == null) {
        
                    p.ns[t] = new Node();
                }
                p = p.ns[t];
                p.min = Math.min(p.min, x);
            }
        }
    
        private int queryMaxXor(int x, int h) {
        
            Node p = root;
            if (p.min > h) {
        
                return -1;
            }
            int res = 0;
            for (int i = 29; i >= 0; i--) {
        
                int t = (x >> i) & 1;
                if (p.ns[t ^ 1] != null && p.ns[t ^ 1].min <= h) {
        
                    res |= 1 << i;
                    t ^= 1;
                }
                p = p.ns[t];
            }
            return res;
        }
    
        public int[] maximizeXor(int[] nums, int[][] queries) {
        
            root = new Node();
            for (int num : nums) {
        
                insert(num);
            }
            int m = queries.length;
            int[] ans = new int[m];
            for (int i = 0; i < m; i++) {
        
                ans[i] = queryMaxXor(queries[i][0], queries[i][1]);
            }
            return ans;
        }
    }

--------------------

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

[1803. 统计异或值在范围内的数对有多少][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`

【**示例**】

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

【**解题思路**】

字典树+计数

class Solution {
        
        class Node{
        
            int count;
            Node[] ns;
            Node () {
        
                count = 0;
                ns = new Node[2];
            }
        }
    
        Node root;
    
        private void insert(int x) {
        
            Node p = root;
            //注意nums[i] <= 2x10^4 , 所以取最大 i << 15
            for (int i = 15; i >= 0; i--) {
        
                int t = (x >> i) & 1;
                if (p.ns[t] == null) {
        
                    p.ns[t] = new Node();
                }
                p = p.ns[t];
                p.count += 1;
            }
        }
    
        private int query(int x, int h) {
        
            int sum = 0;
            Node p = root;
            for (int i = 15; i >= 0; i--) {
        
                if (p == null) break;
                int t = (x >> i) & 1;
                int ht = (h >> i) & 1;
                if (ht == 1) {
        
                    //若上限h当前位为1，则与x相同的位的数异或均小于h
                    if (p.ns[t] != null) {
        
                        sum += p.ns[t].count;
                    }
                    //走向异或结果为1的位置
                    p = p.ns[1 - t];
                } else {
        
                    //走向异或结果为0的位置
                    p = p.ns[t];
                }
            }
            return sum;
        }
    
        public int countPairs(int[] nums, int low, int high) {
        
            root = new Node();
            int res = 0;
            for (int num : nums) {
        
                res += query(num, high + 1) - query(num, low);
                insert(num);
            }
            return res;
        }
    }

[Trie]: https://blog.csdn.net/weixin_44368437/article/details/116640902
[208. _ Trie]: https://leetcode-cn.com/problems/implement-trie-prefix-tree/
[720.]: https://leetcode-cn.com/problems/longest-word-in-dictionary/
[677.]: https://leetcode-cn.com/problems/map-sum-pairs/
[421.]: https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
[1707.]: https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/
[1803.]: https://leetcode-cn.com/problems/count-pairs-with-xor-in-a-range/