146. LRU 缓存 Medium
请你设计并实现一个满足 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) 的平均时间复杂度运行。
示例 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
解题思路
输入： 一个 LRUCache 类
输出： 设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
本题属于哈希表 + 双向链表问题。
我们可以用哈希表记录每个新增的 key 和 value，但记录的 value 可以用一个双向链表包装起来
我们在用两个节点 head tail 分别指向 LRU 和 MRU
哈希表：cache[key] -> 节点对象
双向链表：
head <-> LRU <-> ... <-> MRU <-> tailLRU可以通过head.next找到MRU可以通过tail.prev找到
我们首先设计一个双向链表 Node
还需要实现一个 remove 函数目的是将指定的节点移除，双向链表的好处是可以直接拿到前后节点，互指即可移除当前节点
还需要实现一个 insert 函数目的是将指定节点添加到 MRU(最多使用)，可以通过 tail 节点拿到当前 MRU 节点，指向新插入的节点即可
get 函数我们需要先判断哈希表中是否存在相同 key 的节点，若存在则先移除当前节点再添加到 MRU 即可，若不存在则返回 -1
put 函数我们需要先判断哈希表中是否存在相同 key 的节点，若存在则直接移除，之后创建新的 key value 节点添加至 MRU，最后还要判断是否已经超过最大数量，超过还需要找出 LRU 节点并移除
代码实现
# 定义双向链表的节点结构
class Node:
def __init__(self, key, val):
self.prev = None # 指向前一个节点
self.next = None # 指向后一个节点
self.key = key # 当前节点的 key（用于从字典中删除）
self.val = val # 当前节点的 value（缓存的值）
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity # 缓存最大容量
self.cache = {} # 哈希表：key -> Node
# 创建虚拟头尾节点，方便插入和删除
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
# 从链表中移除某个节点
def remove(self, node):
prev, next = node.prev, node.next
prev.next = next
next.prev = prev
# 将某个节点插入到链表尾部（表示最近使用）
def insert(self, node):
prev, next = self.tail.prev, self.tail
prev.next = node
node.prev = prev
node.next = next
next.prev = node
# 获取值：存在就返回，并把该节点移到链表尾部（最近使用）
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].val # 返回值
return -1 # 不存在则返回 -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])
# 如果超出容量，移除最久未使用节点（头节点后面的第一个）
if len(self.cache) > self.cap:
lru = self.head.next # 最旧的节点
self.remove(lru) # 从链表中移除
del self.cache[lru.key] # 从字典中删除// ES6 的 Map 数据结构天然支持有序存储
// 我们只需要每次 get 和 put 后重新添加进 Map 中就会存储到 Map 的末尾（最多使用）
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.cache = new Map();
this.capacity = capacity;
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.cache.get(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.capacity) {
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey);
}
this.cache.set(key, value);
};复杂度分析
时间复杂度：O(1)
空间复杂度：O(1)