146. 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 <= 30000 <= key <= 100000 <= value <= 1052 * 105 次 get 和 put原站题解
javascript 解法, 执行用时: 508 ms, 内存消耗: 100.3 MB, 提交时间: 2023-09-24 11:48:52
class Node {
constructor(key = 0, value = 0) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.dummy = new Node(); // 哨兵节点
this.dummy.prev = this.dummy;
this.dummy.next = this.dummy;
this.keyToNode = new Map();
}
getNode(key) {
if (!this.keyToNode.has(key)) { // 没有这本书
return null;
}
const node = this.keyToNode.get(key); // 有这本书
this.remove(node); // 把这本书抽出来
this.pushFront(node); // 放在最上面
return node;
}
get(key) {
const node = this.getNode(key);
return node ? node.value : -1;
}
put(key, value) {
let node = this.getNode(key);
if (node) { // 有这本书
node.value = value; // 更新 value
return;
}
node = new Node(key, value) // 新书
this.keyToNode.set(key, node);
this.pushFront(node); // 放在最上面
if (this.keyToNode.size > this.capacity) { // 书太多了
const backNode = this.dummy.prev;
this.keyToNode.delete(backNode.key);
this.remove(backNode); // 去掉最后一本书
}
}
// 删除一个节点（抽出一本书）
remove(x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
// 在链表头添加一个节点（把一本书放在最上面）
pushFront(x) {
x.prev = this.dummy;
x.next = this.dummy.next;
x.prev.next = x;
x.next.prev = x;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
rust 解法, 执行用时: 112 ms, 内存消耗: 101.6 MB, 提交时间: 2023-09-24 11:47:50
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;
struct Node {
key: i32,
value: i32,
prev: Option<Rc<RefCell<Node>>>,
next: Option<Rc<RefCell<Node>>>,
}
impl Node {
fn new(key: i32, value: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node { key, value, prev: None, next: None }))
}
}
struct LRUCache {
capacity: usize,
dummy: Rc<RefCell<Node>>,
key_to_node: HashMap<i32, Rc<RefCell<Node>>>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl LRUCache {
pub fn new(capacity: i32) -> Self {
let dummy = Node::new(0, 0);
dummy.borrow_mut().prev = Some(dummy.clone());
dummy.borrow_mut().next = Some(dummy.clone());
LRUCache { capacity: capacity as usize, dummy, key_to_node: HashMap::new() }
}
pub fn get(&mut self, key: i32) -> i32 {
if let Some(node) = self.key_to_node.get(&key) { // 有这本书
let node = node.clone();
let value = node.borrow().value;
self.remove(node.clone()); // 把这本书抽出来
self.push_front(node); // 放在最上面
return value;
}
-1 // 没有这本书
}
pub fn put(&mut self, key: i32, value: i32) {
if let Some(node) = self.key_to_node.get(&key) { // 有这本书
let node = node.clone();
node.borrow_mut().value = value; // 更新 value
self.remove(node.clone()); // 把这本书抽出来
self.push_front(node); // 放在最上面
return;
}
let node = Node::new(key, value); // 新书
self.key_to_node.insert(key, node.clone());
self.push_front(node); // 放在最上面
if self.key_to_node.len() > self.capacity { // 书太多了
let back_node = self.dummy.borrow().prev.clone().unwrap();
self.key_to_node.remove(&back_node.borrow().key);
self.remove(back_node); // 去掉最后一本书
}
}
// 删除一个节点（抽出一本书）
fn remove(&mut self, x: Rc<RefCell<Node>>) {
let prev = x.borrow().prev.clone().unwrap();
let next = x.borrow().next.clone().unwrap();
prev.borrow_mut().next = Some(next.clone());
next.borrow_mut().prev = Some(prev);
}
// 在链表头添加一个节点（把一本书放在最上面）
fn push_front(&mut self, x: Rc<RefCell<Node>>) {
let next = self.dummy.borrow().next.clone();
x.borrow_mut().prev = Some(self.dummy.clone());
x.borrow_mut().next = next.clone();
self.dummy.borrow_mut().next = Some(x.clone());
next.unwrap().borrow_mut().prev = Some(x);
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* let obj = LRUCache::new(capacity);
* let ret_1: i32 = obj.get(key);
* obj.put(key, value);
*/
golang 解法, 执行用时: 416 ms, 内存消耗: 74.5 MB, 提交时间: 2023-09-24 11:46:48
type entry struct {
key, value int
}
type LRUCache struct {
capacity int
list *list.List // 双向链表
keyToNode map[int]*list.Element
}
func Constructor(capacity int) LRUCache {
return LRUCache{capacity, list.New(), map[int]*list.Element{}}
}
func (c *LRUCache) Get(key int) int {
node := c.keyToNode[key]
if node == nil { // 没有这本书
return -1
}
c.list.MoveToFront(node) // 把这本书放在最上面
return node.Value.(entry).value
}
func (c *LRUCache) Put(key, value int) {
if node := c.keyToNode[key]; node != nil { // 有这本书
node.Value = entry{key, value} // 更新
c.list.MoveToFront(node) // 把这本书放在最上面
return
}
c.keyToNode[key] = c.list.PushFront(entry{key, value}) // 新书，放在最上面
if len(c.keyToNode) > c.capacity { // 书太多了
delete(c.keyToNode, c.list.Remove(c.list.Back()).(entry).key) // 去掉最后一本书
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
cpp 解法, 执行用时: 364 ms, 内存消耗: 161.6 MB, 提交时间: 2023-09-24 11:46:32
class Node {
public:
int key, value;
Node *prev, *next;
Node(int k = 0, int v = 0) : key(k), value(v) {}
};
class LRUCache {
private:
int capacity;
Node *dummy; // 哨兵节点
unordered_map<int, Node*> key_to_node;
// 删除一个节点（抽出一本书）
void remove(Node *x) {
x->prev->next = x->next;
x->next->prev = x->prev;
}
// 在链表头添加一个节点（把一本书放在最上面）
void push_front(Node *x) {
x->prev = dummy;
x->next = dummy->next;
x->prev->next = x;
x->next->prev = x;
}
Node *get_node(int key) {
auto it = key_to_node.find(key);
if (it == key_to_node.end()) // 没有这本书
return nullptr;
auto node = it->second; // 有这本书
remove(node); // 把这本书抽出来
push_front(node); // 放在最上面
return node;
}
public:
LRUCache(int capacity) : capacity(capacity), dummy(new Node()) {
dummy->prev = dummy;
dummy->next = dummy;
}
int get(int key) {
auto node = get_node(key);
return node ? node->value : -1;
}
void put(int key, int value) {
auto node = get_node(key);
if (node) { // 有这本书
node->value = value; // 更新 value
return;
}
key_to_node[key] = node = new Node(key, value); // 新书
push_front(node); // 放在最上面
if (key_to_node.size() > capacity) { // 书太多了
auto back_node = dummy->prev;
key_to_node.erase(back_node->key);
remove(back_node); // 去掉最后一本书
delete back_node; // 释放内存
}
}
};
/**
* 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);
*/
java 解法, 执行用时: 42 ms, 内存消耗: 117.7 MB, 提交时间: 2023-09-24 11:46:15
public class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v) {
key = k;
value = v;
}
}
private final int capacity;
private final Node dummy = new Node(0, 0); // 哨兵节点
private final Map<Integer, Node> keyToNode = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node node = getNode(key);
return node != null ? node.value : -1;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) { // 有这本书
node.value = value; // 更新 value
return;
}
node = new Node(key, value); // 新书
keyToNode.put(key, node);
pushFront(node); // 放在最上面
if (keyToNode.size() > capacity) { // 书太多了
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode); // 去掉最后一本书
}
}
private Node getNode(int key) {
if (!keyToNode.containsKey(key)) { // 没有这本书
return null;
}
Node node = keyToNode.get(key); // 有这本书
remove(node); // 把这本书抽出来
pushFront(node); // 放在最上面
return node;
}
// 删除一个节点（抽出一本书）
private void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
// 在链表头添加一个节点（把一本书放在最上面）
private void pushFront(Node x) {
x.prev = dummy;
x.next = dummy.next;
x.prev.next = x;
x.next.prev = x;
}
}
/**
* 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);
*/
python3 解法, 执行用时: 536 ms, 内存消耗: 75 MB, 提交时间: 2023-09-24 11:45:58
class Node:
# 提高访问属性的速度，并节省内存
__slots__ = 'prev', 'next', 'key', 'value'
def __init__(self, key=0, value=0):
self.key = key
self.value = value
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dummy = Node() # 哨兵节点
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
self.key_to_node = dict()
def get_node(self, key: int) -> Optional[Node]:
if key not in self.key_to_node: # 没有这本书
return None
node = self.key_to_node[key] # 有这本书
self.remove(node) # 把这本书抽出来
self.push_front(node) # 放在最上面
return node
def get(self, key: int) -> int:
node = self.get_node(key)
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self.get_node(key)
if node: # 有这本书
node.value = value # 更新 value
return
self.key_to_node[key] = node = Node(key, value) # 新书
self.push_front(node) # 放在最上面
if len(self.key_to_node) > self.capacity: # 书太多了
back_node = self.dummy.prev
del self.key_to_node[back_node.key]
self.remove(back_node) # 去掉最后一本书
# 删除一个节点（抽出一本书）
def remove(self, x: Node) -> None:
x.prev.next = x.next
x.next.prev = x.prev
# 在链表头添加一个节点（把一本书放在最上面）
def push_front(self, x: Node) -> None:
x.prev = self.dummy
x.next = self.dummy.next
x.prev.next = x
x.next.prev = x
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
python3 解法, 执行用时: 584 ms, 内存消耗: 71.4 MB, 提交时间: 2022-08-02 15:24:36
class ListNode:
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
# 新建两个节点 head 和 tail
self.head = ListNode()
self.tail = ListNode()
# 初始化链表为 head <-> tail
self.head.next = self.tail
self.tail.prev = self.head
# 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法
def move_node_to_tail(self, key):
# 先将哈希表key指向的节点拎出来，为了简洁起名node
# hashmap[key] hashmap[key]
# | |
# V --> V
# prev <-> node <-> next pre <-> next ... node
node = self.hashmap[key]
node.prev.next = node.next
node.next.prev = node.prev
# 之后将node插入到尾节点前
# hashmap[key] hashmap[key]
# | |
# V --> V
# prev <-> tail ... node prev <-> node <-> tail
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key: int) -> int:
if key in self.hashmap:
# 如果已经在链表中了久把它移到末尾（变成最新访问的）
self.move_node_to_tail(key)
res = self.hashmap.get(key, -1)
if res == -1:
return res
else:
return res.value
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
# 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
# 但是需要更新字典该值对应节点的value
self.hashmap[key].value = value
# 之后将该节点移到末尾
self.move_node_to_tail(key)
else:
if len(self.hashmap) == self.capacity:
# 去掉哈希表对应项
self.hashmap.pop(self.head.next.key)
# 去掉最久没有被访问过的节点，即头节点之后的节点
self.head.next = self.head.next.next
self.head.next.prev = self.head
# 如果不在的话就插入到尾节点前
new = ListNode(key, value)
self.hashmap[key] = new
new.prev = self.tail.prev
new.next = self.tail
self.tail.prev.next = new
self.tail.prev = new
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)