Force buckle 146 LRU cache

subject ：

 

analysis ：

You can add a two-way linked list to the hash table ,size Record the amount of data in the current cache ,capacity The maximum amount of data that can be stored in the cache , It is also the input parameter brought when initializing the class ,first,last The two nodes represent the head and tail of the bidirectional linked list respectively , Insert data using tail interpolation , The previous node of the tail node is the most recently used node , The next node of the head node is the most rarely used node , That is to say LRU The one replaced in the algorithm ,hash Responsible for indexing , If there is this index value in the hash , Then he is in the cache , Otherwise, it's not in .

Code ：

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