题解 | #设计LRU缓存结构#

HashMap用来查询，双向链表用来维护最新，效率高于LinkedHashMap


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    //双向链表使用hash表加快访问速度
    class Node{
        int val,key;
        Node pre;
        Node next; 
        public Node(int key,int val){
            this.val=val;
            this.key=key;
            this.pre=null;
            this.next=null;
        }
    }
    
    public int[] LRU (int[][] operators, int k) {
        // write code here
        Node head=new Node(-1,-1);
        Node tail=new Node(-1,-1);
        head.next=tail;
        tail.pre=head;
        Map<Integer,Node> LRU=new HashMap<>();
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                Integer key=new Integer(operators[i][1]);
                Integer value=new Integer(operators[i][2]);
                set(LRU,key,value,k, head, tail);
            }
            else if(operators[i][0]==2){
                int result=get(LRU,operators[i][1],k, head, tail);
                res.add(result);
            }
            
        }
        int []rest=new int[res.size()];
        for(int i=0;i<res.size();i++){
            rest[i]=res.get(i);
        }
        return rest;
        
    }
    public void set(Map<Integer,Node> LRU,Integer key,Integer value,int k,Node head,Node tail){
       if(LRU.containsKey(key)){
           Node tmp=LRU.get(key);
           tmp.pre.next=tmp.next;
           tmp.next.pre=tmp.pre;
           insertTOHead(tmp,head,tail);
           tmp.val=value;
       }
       else{
           if(LRU.size()>=k){
               LRU.remove(tail.pre.key);
               Node p1=tail.pre.pre;
               p1.next=tail;
               tail.pre.pre=null;
               tail.pre.next=null;
               tail.pre=p1;
           }
           Node tmp=new Node(key,value);
           LRU.put(key,tmp);
           insertTOHead(tmp,head,tail);
       }
    }
    public int get(Map<Integer,Node> LRU,Integer key,int k,Node head,Node tail){
        if(!LRU.containsKey(key)){
            return -1;
        }
        else{
            Node tmp=LRU.get(key);
            int res=tmp.val;
            tmp.pre.next=tmp.next;
            tmp.next.pre=tmp.pre;
            insertTOHead(tmp,head,tail);
            return res;
        }
    }
    public void insertTOHead(Node tmp,Node head,Node tail){
        tmp.next=head.next;
        tmp.next.pre=tmp;
        head.next=tmp;
        tmp.pre=head;
    }
}