[数据结构与算法]算法学习-设计数据结构（持续更新中）

哈希

981.基于时间的键值存储

HashMap+数组

class TimeMap {
    class Node{
        String k,v;
        int t;
        public Node(String _k, String _v, int _t){
            k=_k;
            v=_v;
            t=_t;
        }
    } 
    HashMap<String,List<Node>> map=new HashMap<>();
    public void set(String key, String value, int timestamp) {
        List<Node> list=map.getOrDefault(key,new ArrayList<>());
        //set的timestamp都是严格递增的
        list.add(new Node(key,value,timestamp));
        map.put(key,list);
    }
    
    public String get(String key, int timestamp) {
        List<Node> list=map.getOrDefault(key,new ArrayList<>());
        int s=list.size();
        if(s==0) return "";
        //二分查找t<=timestamp的最大值,考虑可能没有这个值
        int left=0;
        int right=s-1;
        while(left<right){
            int mid=(left+right+1)/2;
            if(list.get(mid).t>timestamp){
                right=mid-1;
            }else{
                left=mid;
            }
        }
        //重复判断，如果找到的值不满足
         return list.get(left).t<=timestamp?list.get(left).v:"";
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

缓存

146.LRU缓存

HashMap+手动实现双向链表

hashmap查找一个节点的性能为O(1)-->get
链表对一个节点增删的时间为O(1)，双向链表对一个节点的增删最方便，不需要去找前面的节点–>put、delete

get和put都是需要进行更新的操作，本质上get出来以后需要重新再put进行use更新，get操作可以复用put进行更新。put更新hashmap直接put，更新双向链表删除原来的，加入新的，删除时可以返回key，通过key重新在链表头上加上该node。

对双向链表的delete和addFirst操作都是基于Node的。

class LRUCache {
    HashMap<Integer,Node> map;
    DoubleLinkedList cache;
    int cap;
    public LRUCache(int capacity) {
        map=new HashMap<>();
        cache=new DoubleLinkedList();
        cap=capacity;
    }

    public class Node{
        int k,v;
        Node pre,next;
        public Node(int _k, int _v){
            k=_k;
            v=_v;
        }
    }

    public class DoubleLinkedList{
        Node head,tail;
        public DoubleLinkedList(){
            head=new Node(-1,-1);
            tail=new Node(-1,-1);
            head.next=tail;
            tail.pre=head;
        }
        public int delete(Node n){
            if(head.next==tail) return -1;
            n.next.pre=n.pre;
            n.pre.next=n.next;
            return n.k;
        }
        public int deleteLast(){
            return delete(tail.pre);
        }
        public void addFirst(Node newnode){
            newnode.next=head.next;
            newnode.pre=head;
            head.next.pre=newnode;
            head.next=newnode;
        }
    }
    
    public int get(int key) {
        if(!map.containsKey(key))return -1;
        else{
            int value=map.get(key).v;
            //往双向链表put相同的value
            put(key,value);
            return value;
        }
    }
    
    public void put(int key, int value) {
        Node newnode=new Node(key,value);
        //有相同key的节点进行更新替换
        if(map.containsKey(key)){
            //删除原先双向链表中的该节点,进行更新
            cache.delete(map.get(key));
            cache.addFirst(newnode);
            map.put(key,newnode);
        }else{
            //删除最后未使用的节点
            if(map.size()==cap){
                int k=cache.deleteLast();  
                map.remove(k);
            }
            //一份newnode关联了两个数据结构
            map.put(key,newnode);
            cache.addFirst(newnode);
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

前缀树

关于前缀树的基础知识参考我的另一篇文章，引路->算法学习-字典树

208.实现Trie(前缀树)

class Trie {
    public class Node{
        boolean end;
        Node[] tns=new Node[26];
    }
    public Node root;
    public Trie() {
        root=new Node();
    }
    
    public void insert(String word) {
        Node p=root;
        for(int i=0;i<word.length();i++){
            int u=word.charAt(i)-'a';
            if(p.tns[u]==null) p.tns[u]=new Node();
            p=p.tns[u];
        }
        p.end=true;
    }
    
    public boolean search(String word) {
        Node p=root;
        for(int i=0;i<word.length();i++){
            int u=word.charAt(i)-'a';
            if(p.tns[u]==null) return false;
            p=p.tns[u];
        }
        return p.end;
    }
    
    public boolean startsWith(String prefix) {
        Node p=root;
        for(int i=0;i<prefix.length();i++){
            int u=prefix.charAt(i)-'a';
            if(p.tns[u]==null) return false;
            p=p.tns[u];
        }
        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);
 */

745.前缀和后缀搜索

双字典树+双指针
根据前缀和后缀建立双字典树fronEnd、endFront，字典树节点中list存储以该节点为前缀的元素在数组中的下标。
建立字典树以后，f查询的过程中，根据前缀和后缀检索，得到两棵树对应节点上的下标数组prefNum、suffNum，通过双指针方法从后往前查找，找到相同下标的最大值。

class WordFilter {
    public class Node{
        ArrayList<Integer> list=new ArrayList<>();
        Node[] next=new Node[26];
    }

    //两棵树的根结点
    Node frontEnd= new Node();
    Node endFront=new Node(); 

    //两棵树的建立过程
    public WordFilter(String[] words) {
        for(int i=0;i<words.length;i++){
            String s=words[i];

            Node p=frontEnd;
            Node k=endFront;
            for(int j=0;j<s.length();j++){
                int pidx=s.charAt(j)-'a';
                if(p.next[pidx]==null) p.next[pidx]=new Node();
                p=p.next[pidx];
                p.list.add(i);

                int kidx=s.charAt(s.length()-1-j)-'a';
                if(k.next[kidx]==null) k.next[kidx]=new Node();
                k=k.next[kidx];
                k.list.add(i);
            }
        }
    }
    
    public int f(String pref, String suff) {
        Node p=frontEnd;
        for(int i=0;i<pref.length();i++){
            int prefidx=pref.charAt(i)-'a';
            if(p.next[prefidx]==null) return -1;
            p=p.next[prefidx];
        }
        List<Integer> prefNum=p.list;
        
        Node k=endFront;
        for(int i=0;i<suff.length();i++){
            //注意后缀为倒序
            int suffidx=suff.charAt(suff.length()-1-i)-'a';
            if(k.next[suffidx]==null) return -1;
            k=k.next[suffidx];
        }
        List<Integer> suffNum=k.list;

        int prefNumLen=prefNum.size();
        int suffNumLen=suffNum.size();
        for(int i=prefNumLen-1,j=suffNumLen-1;i>=0&&j>=0;){
            int a=prefNum.get(i);
            int b=suffNum.get(j);
            if(a>b){
                i--;
            }else if(a<b){
                j--;
            }else{
                return a;
            }
        }
        return -1;
    }
}

/**
 * Your WordFilter object will be instantiated and called as such:
 * WordFilter obj = new WordFilter(words);
 * int param_1 = obj.f(pref,suff);
 */

720.词典中最长的单词

构建字典树，记录每个单词结尾节点的end。
对于某个 words[i] 而言，其能成为「合法单词」的充要条件为：words[i] 的每个前缀节点都有end记录。
最后可以返回空并且考虑有多种情况，ans初始化为空字符串""。

class Solution {
    public class Node{
        boolean end;
        Node[] next=new Node[26];
    }
    Node root=new Node();
    public void insert(String s){
        Node p=root;
        for(char c:s.toCharArray()){
            int idx=c-'a';
            if(p.next[idx]==null) p.next[idx]=new Node();
            p=p.next[idx];
        }  
        p.end=true;
    }
    //满足逐步添加单词组成s的条件
    public boolean search(String s){
        Node p=root;
        for(char c:s.toCharArray()){
            int idx=c-'a';
            if(p.next[idx]==null||p.next[idx].end==false) return false;
            p=p.next[idx];
        }
        return p.end;
    }

    public String longestWord(String[] words) {
        //初始化ans为空的字符串
        String ans="";
        for(String s:words)insert(s);
        for(String s:words){
            int n=s.length();
            int m=ans.length();
            //两种剪枝条件
            //排除比答案小的s
            if(n<m) continue;
            //排除字典序大的s
            if(n==m&&s.compareTo(ans)>0) continue;
            if(search(s)) ans=s;
        }
        return ans;
    }   
}

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

我们需要先将 nums 中的数，从高位到低位以二进制的形式加入 Trie树中，开辟大小为2的Node数组，以指针序号表示，每个数字的树深最多为31。
然后对于每个数字，从高位到低位每次贪心的匹配与之不同的二进制位的分支，以此保证异或结果最大。

class Solution {
    public class Node{
        Node[] ns=new Node[2];
    }
    //建树
    Node root=new Node();
    public void add(int num){
        Node p=root;
        for(int i=30;i>=0;i--){
            int idx=(num>>>i)&1;
            if(p.ns[idx]==null) p.ns[idx]=new Node();
            p=p.ns[idx];
        }
    }
    //查找异或最大值
    public int getVal(int num){
        Node p=root;
        int ans=0;
        for(int i=30;i>=0;i--){
            int a=(num>>>i)&1,b=1-a;
            if(p.ns[b]!=null){
                ans|=(b<<i);
                p=p.ns[b];
            }else{
                ans|=(a<<i);
                p=p.ns[a];
            }
        }
        return ans;
    }
    //主方法中找到最大值
    public int findMaximumXOR(int[] nums) {
        int ans=0;
        for(int num:nums){
            add(num);
            int res=getVal(num);
            ans=Math.max(ans,num^res);
        }
        return ans;
    }
}

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

这种提前给定了所有询问的题目，我们可以运用离线思想（调整询问的回答顺序）进行求解，通常做法是对原数组排序，并用map存储原数组的下标对应关系。

1. 对 nums 进行「从小到大」进行排序，对 queries 的第二维进行「从小到大」排序（排序前先将询问原本的下标映射关系用HashMap存下来）。
2. 按照排序顺序处理所有的 queries[i]：
   1. 在回答每个询问前，将小于等于 queries[i][1] 的数值存入字典树。由于我们已经事先对 nums 进行排序，因此这个过程只需要维护一个在 nums 上往右移动的指针一趟即可。
   2. 然后利用贪心思路，查询每个 queries[i][0] 所能找到的最大值是多少，计算异或和，类似于421.数组中两个数的最大异或值
   3. 找到当前询问在原询问序列的下标，将答案存入。

class Solution {
    public class Node{
        Node[]next=new Node[2];
    }
    Node root=new Node();
    public void add(int num){
        Node p=root;
        for(int i=30;i>=0;i--){
            int a=num>>>i&1;
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
    }
    //直接返回最大异或值
    public int getVal(int num){
        Node p=root;
        int ans=0;
        for(int i=30;i>=0;i--){
            int a=num>>>i&1,b=1-a;
            if(p.next[b]!=null){
                ans|=b<<i;
                p=p.next[b];
            }else{
                ans|=a<<i;
                p=p.next[a];
            }
        }
        return ans^num;
    }

    public int[] maximizeXor(int[] nums, int[][] queries) {
        int len1=nums.length;
        int len2=queries.length;
        HashMap<int[],Integer> map=new HashMap<>();
        for(int i=0;i<len2;i++){
            map.put(queries[i],i);
        }
        //进行排序
        Arrays.sort(nums);
        Arrays.sort(queries,(o1,o2)->o1[1]-o2[1]);
        int loc=0;
        int[] ans=new int[len2];
        for(int[]q:queries){
            //加入的是nums中的值
            while(loc<len1&&nums[loc]<=q[1]) add(nums[loc++]);
            //如果没有小于等于q[1]的数字，即loc==0
            if(loc==0){
                ans[map.get(q)]=-1;
            }else{
                ans[map.get(q)]=getVal(q[0]);
            }
        }
        return ans;
    }
}

剑指OfferII065.最短的单词编码

后缀字典树+贪心
根据单词后缀建立字典树，如果能让某个单词尽可能多的包含别的单词（或者说别的单词是字典树的前缀），就能让长度最小。

考虑到最长的单词基本上都需要算入答案，因此先将words按长度降序，将其中不能构成前缀的单词插入字典树，并算入结果的长度。

class Solution {
    public class Node{
        Node[] next=new Node[26];
    }
    Node root=new Node();
    
    //构建字典树
    public void add(String s){
        Node p=root;
        for(int i=s.length()-1;i>=0;i--){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
    }

    //判断s是否为字典树前缀
    public boolean startWith(String s){
        Node p=root;
        for(int i=s.length()-1;i>=0;i--){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) return false;
            p=p.next[a];
        }
        return true;
    }



    public int minimumLengthEncoding(String[] words) {
        int ans=0;
        Arrays.sort(words,(o1,o2)->o2.length()-o1.length());
        for(String s:words){
            if(!startWith(s)){
                add(s);
                ans+=s.length()+1;
            }
        }
        return ans;
    }
}

648.单词替换

简单理解为建立一棵前缀树，然后针对sentence中的所有单词s进行前缀替换，如果能被最前面end域为true的替换则替换，否则还是返回原来的s.

class Solution {
    public class Node{
        boolean isEnd;
        Node[] next=new Node[26];
    }
    Node root=new Node();

    public void add(String s){
        Node p=root;
        for(int i=0;i<s.length();i++){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.isEnd=true;
    }

    //查找最短的词根
    public String query(String s){
        Node p=root;
        for(int i=0;i<s.length();i++){
            int a=s.charAt(i)-'a';
            //这里的逻辑是，如果找不到词根，直接return s
            if(p.next[a]==null) break;
            if(p.next[a].isEnd==true) return s.substring(0,i+1);
            p=p.next[a];
        }
        return s;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        StringBuilder sb= new StringBuilder();
        for(String s:dictionary){
            add(s);
        }
        for(String s:sentence.split(" ")){
            String res=query(s);
            sb.append(res).append(" ");
        }
        return sb.substring(0,sb.length()-1);
    }
}

211.添加与搜索单词

前缀树+DFS
建树过程与模版类似，但由于加入了通配符.，所以其中搜索单词的过程采用dfs控制，分为确定的单词和通配符.两种情况。

class WordDictionary {
    public class Node{
        boolean isEnd;
        Node[]next=new Node[26];
    }
    Node root;
    public WordDictionary() {
        root=new Node();
    }
    
    public void addWord(String word) {
        Node p=root;
        for(int i=0;i<word.length();i++){
            int a=word.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.isEnd=true;
    }
    
    public boolean search(String word) {
        return dfs(word,root,0);
    }
    public boolean dfs(String word,Node root,int index){
        if(index>=word.length()) return root.isEnd;
        if(word.charAt(index)!='.'){
            int a=word.charAt(index)-'a';
            if(root.next[a]==null) return false;
            return dfs(word,root.next[a],index+1);
        }else{
            for(Node n:root.next){
                if(n!=null&&dfs(word,n,index+1)) return true;
            }
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

676.实现一个魔法字典

前缀字典树+DFS
DFS递归函数public boolean query(String s,Node root,int idx,int limit),idx用于表示搜索的层数，可以表示当前搜索到单词的哪一位，limit是限制替换次数的。

对于要search单词的某一位s[idx]而言，我们可以枚举新字符串在当前位置是何种字符的26个字符，若当前枚举到的字符与s[idx]一致，则不消耗替换次数，进入下一层，否则消耗替换次数，进入下一轮。
爆搜过程中替换次数为负数直接return剪枝；当爆搜到结尾位置，再检查当前的节点是否为单词结尾节点，以及剩余的替换次数 limit 是否为 0。

class MagicDictionary {
    public class Node{
        boolean isEnd;
        Node[] next=new Node[26];
    }
    Node root;
    public MagicDictionary() {
        root=new Node();
    }

    public void add(String s){
        Node p=root;
        for(int i=0;i<s.length();i++){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.isEnd=true;
    }

    //递归函数，idx用于表示搜索的层数，limit是限制替换次数的
    public boolean query(String s,Node root,int idx,int limit){
        if(limit<0) return false;
        if(idx==s.length()) return root.isEnd&&limit==0;
        int a=s.charAt(idx)-'a';
        for(int i=0;i<26;i++){
            //该节点没有字符，不能作为替换或者继续递归的入口
            if(root.next[i]==null) continue;
            //query中limit的条件,需要判断这层的字母是否是循环26个字母中的字母
            if(query(s,root.next[i],idx+1,a==i?limit:limit-1)) return true;
        }
        return false;
    }

    public void buildDict(String[] dictionary) {
        for(String s:dictionary) add(s);
    }
    
    public boolean search(String searchWord) {
        return query(searchWord,root,0,1);
    }

    
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * MagicDictionary obj = new MagicDictionary();
 * obj.buildDict(dictionary);
 * boolean param_2 = obj.search(searchWord);
 */

677.键值映射

前缀树+DFS
建立前缀树，单词结尾存储整数值val。然后从前缀末尾开始用dfs统计以该前缀为单词的整数值val。

class MapSum {
    public class Node{
        int val;
        Node[] next=new Node[26];
    }
    Node root;
    public MapSum() {
        root=new Node();
    }

    public void insert(String key, int val) {
        Node p=root;
        for(int i=0;i<key.length();i++){
            int a=key.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.val=val;
    }
    
    public int sum(String prefix) {
        Node p=root;
        for(int i=0;i<prefix.length();i++){
            int a=prefix.charAt(i)-'a';
            if(p.next[a]==null) return 0;
            p=p.next[a];
        }
        return dfs(p);
    }

    public int dfs(Node root){
        if(root==null) return 0;
        int ans=0;
        ans+=root.val;
        for(Node n:root.next){
            ans+=dfs(n);
        }
        return ans;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

472.连接词

前缀树+DFS
先将words按长度从小到大排序，通过DFS判断某个单词是否为连接词，前缀树加入较短的单词，不加入连接词。

class Solution {
    public class Node{
        boolean isEnd;
        Node[] next=new Node[26];
    }

    Node root=new Node();
    public void add(String s){
        Node p=root;
        for(int i=0;i<s.length();i++){
            int a=s.charAt(i)-'a';
            if(p.next[a]==null) p.next[a]=new Node();
            p=p.next[a];
        }
        p.isEnd=true;
    }

    //深搜某个单词是否为连接词,不需要Node root域,全是从字典树的root开始找
    public boolean dfs(String s,int i){
        Node node=root;
        //判断留给下一层，能否直接返回（i已经到s后面一个），或者能够继续往下切割（i指向下一个字符）
        if(s.length()==i) return true;
        while(i<s.length()){
            int a=s.charAt(i)-'a';
            if(node.next[a]==null) return false;
            //node.next[a]不为空，说明字符匹配上了
            node=node.next[a];
            if(node.isEnd==true&&dfs(s,i+1)) return true;
            i++;
        }
        return false;
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words,(o1,o2)->o1.length()-o2.length());
        List<String> ans=new ArrayList<>();
        for(String s:words){
            if(!(s.length()==0)){
                //连接词不需要加入字典树中
                if(dfs(s,0)){
                    //System.out.println(s);
                    ans.add(s);
                }else{
                    add(s);
                }
            }
        }
        return ans;
    }
}