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

java版 LRU 使用hash表和双向链表可以使get和put的时间复杂度都是O(1)
1.put操作：判断缓存是否存在，存在：将hash表的数据进行覆盖，将该链表添加到链表头部；不存在：判断缓存容量是否已满，已满：删除链表尾部节点和hash表内容，最后将新的节点插入到链表头部和添加到hash表中
2：get操作：hash表有则将该节点添加到链表头部，并返回value,没有则返回-1；

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    Map<Integer,Node> map = new HashMap();
    DoubleLinkedList linkedList = new DoubleLinkedList();
    public int[] LRU (int[][] operators, int k) {
        // write code here
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i < operators.length;i++){
            int key =  operators[i][1];
            if(operators[i][0] == 1){
                int val = operators[i][2];
                 Node node = new Node(key,val);
                if(map.containsKey(key)){
                    linkedList.delete(map.get(key));
                    map.put(key,node);
                    linkedList.addFirst(node);

                }else{
                    if(map.size() == k){
                        int k1 = linkedList.deleteTail();
                        map.remove(k1); 
                    }
                    linkedList.addFirst(node);
                    map.put(key,node);
                }

            }else{            
                if(map.containsKey(key)){
                    Node no = map.get(key);
                    list.add(no.val);
                    linkedList.delete(no);
                    linkedList.addFirst(no);

                }else{
                    list.add(-1);
                }
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0;i < list.size();i++){
            res[i] = list.get(i);
        }
        return res;

    }
}
class DoubleLinkedList{
    Node head;
    Node tail;
    DoubleLinkedList(){
        this.head = new Node(0,0);
        this.tail = new Node(0,0);
        head.next = tail;
        tail.pre = head;
    }
    //添加到链表头部
    public void addFirst(Node n){
        n.next = head.next;
        n.pre = head;
        head.next.pre = n;
        head.next = n;

    }
    public int delete(Node n){
        n.pre.next = n.next;
        n.next.pre = n.pre;
        return n.key;
    }

    public int deleteTail(){
        if(head == tail){
            return -1;
        }
        return delete(tail.pre);
    }

}
class Node{
    int key;
    int val;
    Node pre;
    Node next;
    Node(int k,int v){
        this.key = k;
        this.val = v;
    }

}