146.LRU缓存

hash table, doubly-linked list, https://leetcode.cn/problems/lru-cache/

请你设计并实现一个满足 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 <= 10^5
最多调用 2 * 10^5 次 get 和 put

依照力扣题解的提示完成，题解中用书本的抽放来对比十分清楚，dummy是一个同时对书头书尾作处理的节点，next是书头prev是书尾，因此要放到书头或删除书尾都需要dummy帮忙。

双链表的做法用空的头指针和尾指针，方便快速插入到头部和移除尾部。 dict的pop(key)时间复杂度是O(1)！！

首先设置 dummy 头节点和尾节点。当 get 元素时，如果存在就返回值，并将该节点移到头节点；如果不存在就返回-1。当 put 元素时，如果存在就值原地修改，并将该节点移到头节点；如果不存在就在头节点直接插入这个新节点，并判断是否超过了容量，如果超过了就把尾节点删掉。把节点移到头部分为两步：第一步，获得这个节点的 val 值，把它当作一个新节点插入头部；第二步，在链表中删除原来节点。因此只需要两个辅助函数。同时还要注意在超出容量删除尾端元素时要同时把字典里面的这个键值对删去。

python

class DLinkedNode:
    """双向链表的节点类"""
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # 存储 key 到 DLinkedNode 的映射
        # 初始化双向链表
        self.head = DLinkedNode()  # 虚拟头节点
        self.tail = DLinkedNode()  # 虚拟尾节点
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: DLinkedNode):
        """从链表中移除节点"""
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev

    def _insert(self, node: DLinkedNode):
        """将节点插入到链表的头部"""
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        """获取缓存中的值"""
        if key in self.cache:
            node = self.cache[key]
            # 移动到头部
            self._remove(node)
            self._insert(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        """插入/更新键值对"""
        if key in self.cache:
            # 如果键存在，先删除再插入，更新顺序
            node = self.cache[key]
            self._remove(node)
            node.value = value
            self._insert(node)
        else:
            # 如果键不存在，创建新节点
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._insert(node)
            # 如果超过容量，移除最久未使用的元素
            if len(self.cache) > self.capacity:
                # 移除链表尾部的元素，即最久未使用的
                tail = self.tail.prev
                self._remove(tail)
                del self.cache[tail.key]  # dict的pop(key)时间复杂度是O(1)！！


if __name__ == "__main__":
    # 测试代码
    lRUCache = LRUCache(2)
    lRUCache.put(1, 1)
    lRUCache.put(2, 2)
    print(lRUCache.get(1))  # 返回 1
    lRUCache.put(3, 3)  # 该操作会使得关键字 2 作废
    print(lRUCache.get(2))  # 返回 -1 (未找到)
    lRUCache.put(4, 4)  # 该操作会使得关键字 1 作废
    print(lRUCache.get(1))  # 返回 -1 (未找到)
    print(lRUCache.get(3))  # 返回 3
    print(lRUCache.get(4))  # 返回 4

思考题

在本题的基础上，为 key 增加过期时间（put 调用时额外传入过期时间）。如果 key 过期，则需要删除掉。

146.LRU缓存 ​

146.LRU缓存