LRU 缓存

题目描述

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

题解

分析

get 和 put 都需要 O(1) 时间复杂度，我们可以想到两种数据结构：

哈希表读取数据的时间复杂度为 O(1)

双向链表插入删除数据的时间复杂度为 O(1)

那么，我们来分别构造这两个数据结构:

1. 双向链表

在 Python 中是没有指针的概念的，所以我们可以通过自己构造一个 Node 类来当做链表节点，Node 中不仅需要存储 key, value，还需要存储两个指针: 一个指向上一个节点 prev ，另一个指向下一个节点 next

Node

双向链表

2. 哈希表

在 Python 以及大多数编程语言中，都有内置的可靠哈希表实现，我们可以直接使用内置的字典 Dict 来作为哈希表。

哈希表的 key 正常存储 key，value 存储具体的 Node 。

在构造完我们需要的基本数据结构之后，我们再考虑：

❓

如何保证最近使用数据的顺序？

通过在链表的左右端点中安插两个占位节点，保证我们插入和删除数据时，能够找到正确的位置。

例如，我们以链表最左边的节点作为最近使用(most recent)的节点，最右边的节点作为最久未使用(least recent)的节点。

这样，在插入最近使用数据和删除最久没使用的数据时，借助左右两端的两个占位节点，就能很快定位了。

如图所示

❓

如何对链表中的值进行置换？

双向链表的插入和删除操作时间复杂度都是 O(1)

我们分别分析双向链表如何进行插入和删除操作。

插入

以 prev 表示前节点，nxt 表示后节点。

更新 prev.next → 新节点；更新 nxt.pre → 新节点；

新节点.pre → 前节点；新节点.next→ 后节点；

删除

假设当前要删除的节点 Node(2, 2) 为 curr。

前节点 prev 为 curr.pre；后节点 nxt 为 curr.next；

更新前节点指针 prev.next → nxt；更新后节点指针 nxt.pre → prev

接下来，我们再理一下置换的步骤，置换可以分为 get() 时的读置换和 put() 时的写置换。

读置换的步骤：

写置换的步骤：

在厘清这些基本思路之后，我们就可以开始代码实现 👇：

class Node:
    def __init__(self, key, value):
        self.key, self.value = key, value
        self.pre = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}

        # 在左右两个端点中设置两个 dummyNode，dummyNode 其实就是占位符，方便标记位置
        self.left, self.right = Node(0, 0), Node(0, 0)
        # 设定左边是最近使用(most recent), 右边是最久使用(least recent)
        self.left.next, self.right.pre = self.right, self.left 

    def insert(self, node: Node):
        prev, nxt = self.left, self.left.next 
        prev.next = nxt.pre = node
        node.pre, node.next = prev, nxt
    
    def remove(self, node):
        prev, nxt = node.pre, node.next
        prev.next, nxt.pre = nxt, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].value
        return -1

    def put(self, key: int, value: int) -> None:
        # 先删后插
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        # 先删除链表，在删除 cache
        if len(self.cache) > self.cap:
            lru = self.right.pre
            self.remove(lru)
            del self.cache[lru.key]



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)