LeetCode：排序树，字典树

1，递增序列

220，存在重复元素 III

题目：给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。

思路：滑动窗口+排序树

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < n; i++) {
            Long ceiling = set.ceiling((long) nums[i] - (long) t);
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }
}

334，递增的三元子序列（123模式）

题目：给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

class Solution {
    public boolean increasingTriplet(int[] nums) {
        int a = 2147483647, b = a;
    for (int n: nums) 
        if (n <= a) a = n;
        else if (n <= b) b = n;
        else return true;
    return false;
    }
}

456，132模式

题目：给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。

class Solution {
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Deque<Integer> candidateK = new LinkedList<Integer>();
        candidateK.push(nums[n - 1]);
        int maxK = Integer.MIN_VALUE;

        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < maxK) {
                return true;
            }
            while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
                maxK = candidateK.pop();
            }
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }

        return false;
    }
}

1855，12模式（下标对中最大距离）

题目：给你两个 非递增 的整数数组 nums1​​​​​​ 和 nums2​​​​​​ ，数组下标均 从 0 开始 计数。下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <=j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i​​ 。​​返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int left = 0;
        int right = 0;
        int result = 0;
        while (left < nums1.length && right < nums2.length) {
            if (left < right && nums1[left] <= nums2[right]) {
                result = Math.max(result, right - left);
                right++;
            } else if (left < right && nums1[left] > nums2[right]) {
                left++;
            } else if (left > right) {
                right++;
            } else if (left == right && nums1[left] <= nums2[right]) {
                result = Math.max(result, right - left);
                right++;
            } else if (left == right && nums1[left] > nums2[right]) {
                left++;
            }
        }
        return result;
    }
}

2，字典树（前缀树）

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 。

思路：

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

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

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

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0; // 两个非负数的异或必为非负数
        Trie trie = new Trie();
        for(int num : nums){
            trie.insert(num);
            max = Math.max(max, num ^ trie.search(num));
        }
        return max;
    }
}

class Trie{
    Trie[] next;
    public Trie(){
        this.next = new Trie[2];
    }
    public void insert(int num){
        Trie cur = this;
        for(int i = 30; i >= 0; i--){ // 题目范围为非负数，高31位移动到低1位只要右移30位
            int bit = (num >> i) & 1;
            if(cur.next[bit] == null){
                cur.next[bit] = new Trie();
            } 
            cur = cur.next[bit];
        }
    }
    public int search(int num){ // 返回当前前缀树中与num做异或能够取得最大值的数字。取出后再在外部做异或运算。
        Trie cur = this;
        int ans = 0; 
        for(int i = 30; i >= 0; i--){
            int bit = (num >> i) & 1; // 取得当前位（0或1）
            bit = cur.next[bit ^ 1] == null ? bit : bit ^ 1; // 与bit相反（指0-1相反）的节点若不存在，bit不变，若存在，取相反
            ans += bit << i; // 累计ans
            cur = cur.next[bit]; 
        }
        return ans;
    }
}

648，单词替换

题目：在英语中，我们有一个叫做 词根(root) 的概念，可以词根后面添加其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，跟随着单词 other(其他)，可以形成新的单词 another(另一个)。

现在，给定一个由许多词根组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。

你需要输出替换之后的句子。

class Solution {

    class TrieNode{
        TrieNode[] next;
        String word;

        public TrieNode(){
            this.next = new TrieNode[26];
            this.word = null;
        }
    }

    private TrieNode tRoot = new TrieNode();

    public String replaceWords(List<String> dictionary, String sentence) {
        //先将所有的词根加入到Trie中
        for(String s : dictionary){
            add(s);
        }
        //拆分sentence
        String[] sp = sentence.split(" ");
        
        //遍历sp，在Trie中搜索是否有可以替代的词根
        for(int i = 0;i < sp.length;i++){
            String root = get(sp[i]);
            //如果root不为null则找到了可以替代的词根，将此处的原单词替换为词根
            if(root != null){
                sp[i] = root;
            }
        }
        //最后再把sp数组用空格分隔拼接成一个串返回即可
        return String.join(" ",sp);
    }

    public void add(String str){
        TrieNode node = tRoot;
        for(char c : str.toCharArray()){
            if(node.next[c - 'a'] == null){
                node.next[c - 'a'] = new TrieNode();
            }
            node = node.next[c - 'a'];
        }
        //把整个单词都加进Trie中之后，在最后面挂上word
        node.word = str;
    }

    public String get(String str){
        TrieNode node = tRoot;

        for(char c : str.toCharArray()){
            //如果遇到了词根了，直接break，此时遇到的词根符合题目“最短词根的要求”
            if(node.word != null){
                break;
            }
            //走到这里就是还没遇到词根，如果在没遇到词根就不满足条件了，直接返回null
            if(node.next[c - 'a'] == null){
                return null;
            }
            //迭代
            node = node.next[c - 'a']; 
        }
        return node.word;
    }
}

676，实现一个魔法字典

题目：设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同 。 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。

实现 MagicDictionary 类：

• MagicDictionary() 初始化对象
• void buildDict(String[] dictionary) 使用字符串数组 dictionary 设定该数据结构，dictionary 中的字符串互不相同
• bool search(String searchWord) 给定一个字符串 searchWord ，判定能否只将字符串中 一个 字母换成另一个字母，使得所形成的新字符串能够与字典中的任一字符串匹配。如果可以，返回 true ；否则，返回 false 。

class MagicDictionary {
    HashMap<String, Integer> map;
    HashSet<String> set;
    /** Initialize your data structure here. */
    public MagicDictionary() {
        map = new HashMap<>();
        set = new HashSet<>();
    }
    
    public void buildDict(String[] dictionary) {
        for(String s: dictionary){
            set.add(s);
            StringBuffer sb = new StringBuffer(s);
            for(int i=0; i<sb.length(); i++){
                sb.setCharAt(i, '*');
                map.put(sb.toString(), map.getOrDefault(sb.toString(), 0)+1);
                sb.setCharAt(i, s.charAt(i));
            }
        }
    }
    
    public boolean search(String searchWord) {
        StringBuffer sb = new StringBuffer(searchWord);
        for(int i=0; i<sb.length(); i++){
            sb.setCharAt(i, '*');
            String s = sb.toString();
            if(map.containsKey(s)){
                if(map.get(s) > 1) return true;
                if(map.get(s) == 1 && !set.contains(searchWord)) return true;  
            }
            sb.setCharAt(i, searchWord.charAt(i));
        }
        return false;
    }
}

677，键值映射

题目：设计一个 map ，满足以下几点:

• 字符串表示键，整数表示值
• 返回具有前缀等于给定字符串的键的值的总和

实现一个 MapSum 类：

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

class MapSum {

    class TreeNode{
        boolean isEnd;
        int val;
        TreeNode[] tns = new TreeNode[26];
    }

    TreeNode root;
    int sum;
    public MapSum() {
        root = new TreeNode();
    }
    
    public void insert(String key, int val) {
        TreeNode p = root;
        for(char ch : key.toCharArray()){
            int temp = ch - 'a';
            if(p.tns[temp] == null){
                p.tns[temp] = new TreeNode();
            }
            p = p.tns[temp];
        }
        p.isEnd = true;
        p.val = val;
    }
    
    public int sum(String prefix) {
        sum = 0;
        TreeNode p = root;
        for(char ch : prefix.toCharArray()){
            int temp = ch - 'a';
            if(p.tns[temp] == null){
                return sum;
            }
            p = p.tns[temp];
        }
        find(p);
        return sum;
    }

    public void find(TreeNode p){
        if(p.isEnd == true){
            sum += p.val;
        }
        for(int i = 0;i < 26;i++){
            if(p.tns[i] != null){
                find(p.tns[i]);
            }
        }
        return;
    }
}

720，词典中最长的单词

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

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        String ans = "";
        Trie trie = new Trie();
        for (String s : words) {
            trie.insert(s);
            if (trie.inDictionary(s) && s.length() > ans.length()) {
                ans = s;
            }
        }
        return ans;
    }
}
class Trie {
    TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }

    void insert(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            if (cur.children[c - 'a'] == null) {
                cur.children[c - 'a'] = new TrieNode();
            }
            cur = cur.children[c - 'a'];
        }
        cur.exist = true;
    }

    boolean inDictionary(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null || !cur.exist) {
                return false;
            }
        }
        return true;
    }
}
class TrieNode {
    boolean exist;
    TrieNode[] children;

    TrieNode() {
        exist = false;
        children = new TrieNode[26];
    }
}

820，单词的压缩编码

题目：单词数组 words 的 有效编码 由任意助记字符串 s 和下标数组 indices 组成，且满足：

• words.length == indices.length
• 助记字符串 s 以 '#' 字符结尾
• 对于每个下标 indices[i] ，s 的一个从 indices[i] 开始、到下一个 '#' 字符结束（但不包括 '#'）的 子字符串 恰好与 words[i] 相等

给你一个单词数组 words ，返回成功对 words 进行编码的最小助记字符串 s 的长度 。

思路：目标就是保留所有不是其他单词后缀的单词。

class Solution {
    public int minimumLengthEncoding(String[] words) {
        TrieNode trie = new TrieNode();
        Map<TrieNode, Integer> nodes = new HashMap<TrieNode, Integer>();

        for (int i = 0; i < words.length; ++i) {
            String word = words[i];
            TrieNode cur = trie;
            for (int j = word.length() - 1; j >= 0; --j) {
                cur = cur.get(word.charAt(j));
            }
            nodes.put(cur, i);
        }

        int ans = 0;
        for (TrieNode node: nodes.keySet()) {
            if (node.count == 0) {
                ans += words[nodes.get(node)].length() + 1;
            }
        }
        return ans;

    }
}

class TrieNode {
    TrieNode[] children;
    int count;

    TrieNode() {
        children = new TrieNode[26];
        count = 0;
    }

    public TrieNode get(char c) {
        if (children[c - 'a'] == null) {
            children[c - 'a'] = new TrieNode();
            count++;
        }
        return children[c - 'a'];
    }
}

最后

以上就是受伤中心最近收集整理的关于LeetCode：排序树，字典树的全部内容，更多相关LeetCode：排序树内容请搜索靠谱客的其他文章。