数据结构 - wenzhoullq/leetcode GitHub Wiki

慢追快

在排好序的情况下用栈模拟是否能够碰到

题目

735. 行星碰撞

853. 车队先排序，直线斜率的方式可以避免精度问题，但是注意用long防止溢出

删除

构造一个链表，链表里记录的是未被删除的下标，然后对未被删除的进行遍历，实现动态的删除效果

题目

843. 猜猜这个单词

加密

加密是对所有的需要加密的字符串进行加密，存储在映射表里，自行解密是无法解密的

题目

2227. 加密解密字符串

迭代器

用增强for循环迭代

题目

341. 扁平化嵌套列表迭代器

复制

用HashMap保持映射，然后进行复制

题目

133. 克隆图

138. 复制带随机指针的链表

栈

题目

155. 最小栈

895. 最大频率栈维护一个频率栈的list和各个数字的频率

常见数据结构

题目

字典树

字典树和前缀强相关，涉及到前缀可以考虑字典树,另一点值得注意的是,字符是在trie.tries[]里,trie并非是当前字符

class Trie {
    Trie[] trie;
    boolean visit;
    public Trie() {
        trie=new Trie[26];
        visit=false;
    }
    public void insert(String word) {
        Trie p=this;
        for(int i=0;i<word.length();i++){
            int c=word.charAt(i)-'a';
            if(p.trie[c]==null) p.trie[c]=new Trie();
            p=p.trie[c];
        }
        p.visit=true;
    }
    
    public boolean search(String word) {
        Trie p=this;
        for(int i=0;i<word.length();i++){
            int c=word.charAt(i)-'a';
            if(p.trie[c]==null) return false;
            p=p.trie[c];
        }
        return p.visit;
    }
    
    public boolean startsWith(String prefix) {
        Trie p=this;
        for(int i=0;i<prefix.length();i++){
            int c=prefix.charAt(i)-'a';
            if(p.trie[c]==null) return false;
            p=p.trie[c];
        }
        return true;
    }   
}

题目

208. 实现 Trie (前缀树)

211. 添加与搜索单词 - 数据结构设计

212. 单词搜索 II 字典树剪枝

386. 字典序排数

1032. 字符流倒着建树

6183. 字符串的前缀分数和

01-trie


    class Trie{
        Trie[] Tries = new Trie[2];
        int get(){
            int ans = 0;
            Trie p = this;
            for(int i = 31; i>=0;i--){
                
            }
            return ans;
        }
        void add(int num){
            Trie p = this;
            for(int i = 31;i>=0 ;i--){
                int n = (num>>i)&1;
                if(p.Tries[n]==null) p.Tries[n] = new Trie();
                p = p.Tries[n];
            }
        }
    }

对于^的题目用01-trie来求解,难点在于如何get

421. 数组中两个数的最大异或值 add在get之前

1803. 统计异或值在范围内的数对有多少 add在get之后，有一点数位DP的思想

TreeSet/TreeMap/优先队列

一般情况下，能使用优先队列就使用优先队列，优先队列的底层是数组，但是优先队列有个致命的弱点，就是无法O(1)的取特定的数字，此时需要使用TreeMap/TreeSet替代

题目

855. 考场就座

1825. 求出 MK 平均值三个TreeSet模拟

6130. 设计数字容器系统

6126. 设计食物评分系统（注意拆包问题）