题目146. LRU 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出

[null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

解法 HashMap + 双向链表

看到题目要求get和put的时间复杂度为O(1)，自然是要利用哈希表的高效查询和插入功能。

需要用一个数据结构来储存优先级，需要支持从数据结构中抽出一个元素放到链头

这里首先考虑到用链表，但是用单向链表的话不好找上一个节点，不能抽出来节点

而用双向链表 在hashMap中直接保存指向链表中对应节点的指针，就可以直接得到前面和后面的节点，支持把节点抽出来！

用一个HashMap保存 key 到 ListNode的映射，将key和value保存在链表中。

class LRUCache {
    private class ListNode {
        int key;
        int val;
        ListNode pre;
        ListNode next;
        ListNode() {}
        ListNode(int key, int val) {this.key = key; this.val = val;}
        ListNode(int val, ListNode pre, ListNode next) {
            this.val = val;
            this.pre = pre;
            this.next = next;
        }
    } 

    private ListNode headNode;
    private ListNode tailNode;

    private Map<Integer, ListNode> map = new HashMap<>();
    private int capacity;
    private int currentCapacity = 0;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            ListNode tempNode = map.get(key);
            moveToHead(tempNode);
            return tempNode.val;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode tempNode = map.get(key);
            tempNode.val = value;
            moveToHead(tempNode);
        } else {
            // 没找到
            ListNode tempNode = new ListNode(key, value);
            map.put(key, tempNode);   
            while (currentCapacity >= capacity) {
                // 已经满了，删除链尾，加在链头
                map.remove(tailNode.key);
                tailNode = tailNode.pre;
                if (tailNode != null) tailNode.next = null;
                currentCapacity--;
            }
            if (currentCapacity == 0) {
                headNode = tempNode;
                tailNode = tempNode;
                currentCapacity++;
                return;
            }
            addToHead(tempNode);
        }
    }

    private void addToHead(ListNode node) {
        node.next = headNode;
        headNode.pre = node;
        headNode = node;
        currentCapacity++;
    }

    private void moveToHead(ListNode node) {
        ListNode preNode = node.pre, postNode = node.next;
        if (preNode == null) return;
        if (postNode == null) {
            tailNode = preNode;
        } else {
            postNode.pre = preNode;
        }
        preNode.next = postNode;
        headNode.pre = node;
        node.next = headNode;
        node.pre = null;
        headNode = node;
    }
}

时间复杂度为O(1)!