[数据结构与算法]力扣 146. LRU 缓存

题目：

?

分析：

可以用哈希表加一个双向链表来实现，size记录当前缓存中数据量，capacity存缓存中数据可以容纳的最大量，也是初始化类的时候带的入参，first，last两个节点分别代表双向链表的头和尾，使用尾插法插入数据，尾结点的前一个结点为最近使用结点，头结点的下一个结点为最近不常用结点，也就是LRU算法中被替换掉的那一个，hash负责存索引，如果哈希中有这个索引值，则他在缓存中，否则不在。

代码：

class LRUCache {
    class Node{
        int key;
        int val;
        Node next;
        Node pre;
        public Node(){}
        public Node(int key,int val){
            this.key=key;
            this.val=val;
            this.next=null;
            this.pre=null;
        }
    }
    HashMap<Integer,Node> hash=new HashMap<Integer,Node>();
    int size;
    int capacity;
    Node first;
    Node last;
    public LRUCache(int capacity) {
        this.size=0;
        this.capacity=capacity;
        this.first=new Node();
        this.last=new Node();
        first.next=last;
        last.pre=first;
    }
    
    public int get(int key) {
        Node n=hash.get(key);
        if(n!=null){
            Node pre=n.pre;
            Node nex=n.next;
            if(nex!=last){
                nex.pre=pre;
                pre.next=nex;
                n.pre=last.pre;
                last.pre.next=n;
                n.next=last;
                last.pre=n;
            }
            return n.val;
        }else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        Node n=hash.get(key);
        if(n!=null){
            Node pre=n.pre;
            Node nex=n.next;
            if(nex!=last){
                nex.pre=pre;
                pre.next=nex;
                n.pre=last.pre;
                last.pre.next=n;
                n.next=last;
                last.pre=n;
            }
            n.val=value;
        }else{
            if(size==capacity){
                int k=first.next.key;
                hash.remove(k);
                first.next=first.next.next;
                first.next.pre=first;
                size--;
            }
            n=new Node(key,value);
            n.pre=last.pre;
            last.pre.next=n;
            n.next=last;
            last.pre=n;
            hash.put(key,n);
            size++;
        }
    }
}

/**
 * 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);
 */