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

汇总和整理算法题中设计数据结构的题目，增强数据结构融会贯通的能力。

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> map=new HashMap<>();
    public void set(String key, String value, int timestamp) {
        List 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 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
            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:"";
    }
}

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 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);
        }
    }
}