[Leetcode 146] LRU 缓存

• LRUCache(int capacity) ：以 正整数 作为容量 capacity 初始化 LRU 缓存。

• int get(int key) ： 如果key 存在，返回的值 ，否则返回 -1.

• void put(int key, int value) ：
• 如果key 存在，更新key 的值 。
• 否则，添加 key-value 对。
• 如果key的数量超过 capacity ， 删除最近最少使用的key。

解法一：直接用 OrderedDict

• 它内部已经按插入顺序维护键的顺序；

• move_to_end(key)：把某个 key 挪到末尾，相当于“标记为最近用过”；

• popitem(last=False)：弹出最前面的元素，相当于“淘汰最久未使用”的那个。

• 时间复杂度：get / put 均为均摊 O(1)；

• 空间复杂度：O(capacity)。

解法二：哈希表 + 双向链表（推荐）

1. O(1) 查找 key → value
用哈希表（dict）来做：key -> 链表节点 Node。

2. 按“访问先后”维护一个队列，能快速移动一个节点到“最新”位置，快速淘汰“最旧”的那个
用双向链表：
• 靠近链表头部的是最近访问的；
• 靠近尾部的是最久未访问的。
get / put 的操作都要连带更新链表的顺序：
• get(key)：
• 如果没找到，返回 -1。
• 找到了，把这个节点从原位置“摘”出来，挪到头部（标记为“刚用过”），然后返回值。
• put(key, value)：
• 如果 key 已经存在：
• 更新节点 value；
• 把节点挪到头部。
• 如果 key 不存在：
• 创建新节点，挂到头部；
• 写进哈希表；
• 如果容量爆了，就从链表尾部删掉一个节点（最久未使用），顺便从哈希表删掉对应 key。

• head：最前面一个伪头，不存真实数据；

• tail：最后一个伪尾，也不存真实数据。

• 时间复杂度：get、put 都是 O(1)：
• 哈希查找是 O(1)；
• 双向链表增删节点也是 O(1)。

• 空间复杂度：O(capacity)，哈希表和链表最多存 capacity 个节点。

解法三：把“删/插”封装成 Node 的方法

• node.delete()：把当前节点从链表中摘掉；

• node.insert(prev_node)：把当前节点插入到 prev_node 后面。

• LRUCache 核心逻辑读起来更像“操作一个对象”，而不是堆满指针细节；

• 指针操作都集中在 Node 类里，不到处复制粘贴，减少写错的概率。

• 时间复杂度：get / put 依然是 O(1)；

• 空间复杂度：O(capacity)。