146. LRU 缓存机制

题目：146. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
3. void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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 <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put
链接：https://leetcode-cn.com/problems/lru-cache

解题思路

/*
    LRU缓存淘汰算法：最近最少使用
    思路一：直接用LinkedHashMap，容器内部就实现了LRU算法。
		LinkedHashMap的有序可以按两种顺序排列，一种是按照插入的顺序，一种是按照读取的顺序（这个题目的示例就是告诉我们要按照读取的顺序进行排序）
    链接：https://leetcode-cn.com/problems/lru-cache/solution/yuan-yu-linkedhashmapyuan-ma-by-jeromememory/
    思路二： 哈希表 + 双向链表
    1.哈希表用于满足题目时间复杂度O(1)的要求，双向链表用于存储顺序
    2.哈希表键值类型：<Integer, ListNode>，哈希表的键用于存储输入的key，哈希表的值用于存储双向链表的节点
    3.双向链表的节点中除了value外还需要包含key，因为在删除最久未使用的数据时，需要通过链表来定位hashmap中应当删除的键值对
    4.一些操作：双向链表中，在后面的节点表示被最近访问
        i. 新加入的节点放在链表末尾，addNodeToLast(node)
        ii. 若容量达到上限，去除最久未使用的数据，removeNode(head.next)
        iii. 若数据新被访问过，比如被get了或被put了新值，把该节点挪到链表末尾，moveNodeToLast(node)
    5.为了操作的方便，在双向链表头和尾分别定义一个head和tail节点。
    复杂度分析：
        时间复杂度：O(1)
        空间复杂度：O(capacity)
    链接：https://leetcode-cn.com/problems/lru-cache/solution/bu-yong-yu-yan-nei-jian-de-map-gua-dang-feng-zhuan/
    */

解题方法一：LinkedHashMap

https://leetcode-cn.com/problems/lru-cache/solution/yuan-yu-linkedhashmapyuan-ma-by-jeromememory/

 // 思路一：直接用LinkedHashMap
 class LRUCache extends LinkedHashMap<Integer, Integer> {
        private int capacity;
        public LRUCache(int capacity) {
            // accessOrder=false按照插入顺序，accessOrder=true按照读取顺序
            super(capacity, 0.75F, true);
            this.capacity = capacity;
        }
        public int get(int key) {
            return super.getOrDefault(key, -1);
        }
        // 这个可不写
        public void put(int key, int value) {
            super.put(key, value);
        }
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    } 

解题方法二：哈希表 + 双向链表

https://leetcode-cn.com/problems/lru-cache/solution/bu-yong-yu-yan-nei-jian-de-map-gua-dang-feng-zhuan/

// 思路二：哈希表 + 双向链表
class LRUCache {
    int capacity;               // 缓存的容量
    Map<Integer, ListNode> map; // 哈希表
    int count;                  // 缓存数目
    ListNode dummyHead;         // 虚拟头结点
    ListNode dummyTail;         // 虚拟尾节点

    public LRUCache(int capacity) {
        this.capacity = capacity;               // 缓存的容量
        this.map = new HashMap<>();             // 哈希表
        this.count = 0;                         // 缓存数目
        this.dummyHead = new ListNode(-1);  // 虚拟头结点
        this.dummyTail = new ListNode(-1);  // 虚拟尾节点
        this.dummyHead.next = this.dummyTail;
        this.dummyTail.prev = this.dummyHead;   // 相联系
    }
    public int get(int key) {
        ListNode node = map.get(key);       // 从哈希表中，获取对应的节点
        if (null == node) return -1;        // 如果节点不存在，返回-1
        this.moveToTail(node);              // 被读取了，该节点移动到链表尾部
        return node.val;                    // 返回出节点值
    }
    private void moveToTail(ListNode node) {
        this.removeFromList(node);      // 从链表中删除节点
        this.addToTail(node);           // 放入链表尾部
    }
    private void removeFromList(ListNode node) {
        ListNode next = node.next;  // 暂存它的后继节点
        ListNode pre = node.prev;   // 暂存它的前驱节点
        pre.next = next;            // 前驱节点的next指向后继节点
        next.prev = pre;            // 后继节点的prev指向前驱节点
    }
    private void addToTail(ListNode node) { // 插入到虚拟头结点和真实头结点之间
        ListNode tail = dummyTail.prev;     // 获得尾结点
        tail.next = node;                   // 尾结点的后继指向该节点
        node.prev = tail;                   // 该节点的前驱指向尾结点
        node.next = dummyTail;              // 该节点的后继指向虚拟尾结点
        dummyTail.prev = node;              // 虚拟尾结点的前驱指向该节点
    }

    public void put(int key, int value) {
        ListNode node = map.get(key);               // 获取链表中的node
        if (null == node) {                         // 不存在于链表，是新数据
            if (this.count == this.capacity) {      // 容量已满
                this.removeLRUItem();               // 删除最远一次使用的数据
            }
            ListNode newNode = new ListNode(key, value); // 创建新的节点
            map.put(key, newNode);                  // 存入哈希表
            this.addToTail(newNode);                // 将节点添加到链表尾部
            this.count++;                           // 缓存数目+1
        } else {                                    // 已经存在于链表，老数据
            node.val = value;                       // 更新value
            this.moveToTail(node);                  // 将节点移到链表尾部
        }
    }
    // 删除最远一次使用的数据 ,头部一直是最老的老家伙
    private void removeLRUItem() {              // 删除“老家伙”
        ListNode head = this.dummyHead.next;    // 通过虚拟头节点找到它
        this.removeFromList(head);              // 删除该真实头节点
        map.remove(head.getKey());              // 哈希表中也将它删除
        this.count -- ;                         // 缓存数目-1
    }
}
public class ListNode {
    // 单链表
    int val;
    ListNode next;
    // 添加下面是双向链表
    ListNode prev;
    int key;

    ListNode(int x) { val = x; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    ListNode(int key, int val) { this.key = key; this.val = val; }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    public ListNode getPrev() {
        return prev;
    }

    public void setPrev(ListNode prev) {
        this.prev = prev;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }
}
/**
 * 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);
 */