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

这题面试的概率非常的搞，按照LRU的算法逻辑。每次都是将容量内最久没有使用的来移除。 思路：

1. 每次把新鲜的数据向链表的表头来移动。最新移动的数据：1. 修改(put)，或者访问过(get)。

2. 每次在插入数据的时候，检查当前的LRU容量，是否已经满了，如果满了，把最旧的移除（也就是链表最后的一个节点）。

3. 每次我们把LRU的内容都存放在一个hash表内<key, 节点>，这样查找的时候就不用需要去遍历链表了。

4. 在链表中维护当前的优先级别，把最新鲜的数据放到列表头：

我们来模拟一下案例：

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

1. 开始的时候初始：
2. 后续

按照上面的规律，每次有新鲜数据，都把他放到队列的头部。每次需要删除的时候都要删除链表最后的末尾元素。

代码：

class LRUCache {
    class Node{
        Node left, right;
        public int key, val;
        public Node(int key, int val){
            this.key = key;
            this.val = val;
            left = null;
            right = null;
        }
    }

    Map<Integer, Node> hash  = new HashMap<>();
    int n;
    Node ll, rr;

    public LRUCache(int capacity) {
        n = capacity;
        ll = new Node(-1, -1);
        rr = new Node(-1, -1);
        ll.right = rr;
        rr.left = ll;
    }
    
    public int get(int key) {
        if(!hash.containsKey(key)) return -1;
        Node node = hash.get(key);
        // 将当前节点移动到最前端
        remove(node);
        insert(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(hash.containsKey(key)){
            Node node = hash.get(key);
            node.val = value;
            remove(node);
            insert(node);
        }else{
            // 表示当前的数量已经满了
            if(hash.size() == n){
                // 删除最后的节点
                Node p = rr.left;
                hash.remove(p.key);
                remove(p);
            }
            // 插入节点
            Node node = new Node(key, value);
            hash.put(key, node);
            insert(node); // 插入到头结点
        }
    }

    public void remove(Node node){
        node.left.right = node.right;
        node.right.left = node.left;
    }

    public void insert(Node node){
        node.right = ll.right;
        node.left = ll;
        ll.right.left = node;
        ll.right = node;
    }
}