剑指 Offer II 031. 最近最少使用缓存

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20031.%20%E6%9C%80%E8%BF%91%E6%9C%80%E5%B0%91%E4%BD%BF%E7%94%A8%E7%BC%93%E5%AD%98/README.md

剑指 Offer II 031. 最近最少使用缓存

题目描述

运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例：

输入
["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⁵
最多调用 2 * 10⁵ 次 get 和 put

进阶：是否可以在 O(1) 时间复杂度内完成这两种操作？

注意：本题与主站 146 题相同：https://leetcode.cn/problems/lru-cache/

解法

方法一：哈希表 + 双向链表

我们可以用“哈希表”和“双向链表”实现一个 LRU 缓存。

哈希表：用于存储 key 和对应的节点位置。
- 双向链表：用于存储节点数据，按照访问时间排序。o(1)

当访问一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点。

当插入一个节点时，如果节点存在，我们将其从原来的位置删除，并重新插入到链表头部。如果不存在，我们首先检查缓存是否已满，如果已满，则删除链表尾部的节点，将新的节点插入链表头部。

时间复杂度 $O (1)$ ，空间复杂度 $O (c a p a c i t y)$ 。

Python3

class Node:def __init__(self,key=0,val=0):self.key=keyself.val=valself.prev=Noneself.next=Noneclass LRUCache:def __init__(self, capacity: int):self.cache={}self.capacity=capacity#重要标记： 方便o(1)插入首尾，达到 （链头：最近 链位：最久）self.head=Node()self.tail=Node()self.head.next=self.tailself.tail.prev=self.headself.len=0def get(self, key: int) -> int:if key not in self.cache:return -1Nd=self.cache[key]self.exist_to_head(Nd)return Nd.valdef put(self, key: int, value: int) -> None:if key in self.cache:Nd=self.cache[key]Nd.val=valueself.exist_to_head(Nd)else:Nd=Node(key,value)self.put_to_head(Nd)self.len+=1self.cache[key]=Ndif self.len>self.capacity: #注意1位置：先增后删的意义！！！Nd=self.del_tail()self.len-=1del self.cache[Nd.key]def put_to_head(self,node):node.next=self.head.nextnode.prev=self.headnode.next.prev=nodeself.head.next=nodedef del_tail(self):del_node=self.tail.prevprv_node=del_node.prevprv_node.next=self.tailself.tail.prev=prv_nodereturn del_nodedef exist_to_head(self,node):#先 delprv_node=node.prevnx_node=node.nextprv_node.next=nx_nodenx_node.prev=prv_node#再 put_to_headself.put_to_head(node)# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

Java

class Node {int key;int val;Node prev;Node next;Node() {}Node(int key, int val) {this.key = key;this.val = val;}
}class LRUCache {private Map<Integer, Node> cache = new HashMap<>();private Node head = new Node();private Node tail = new Node();private int capacity;private int size;public LRUCache(int capacity) {this.capacity = capacity;head.next = tail;tail.prev = head;}public int get(int key) {if (!cache.containsKey(key)) {return -1;}Node node = cache.get(key);moveToHead(node);return node.val;}public void put(int key, int value) {if (cache.containsKey(key)) {Node node = cache.get(key);node.val = value;moveToHead(node);} else {Node node = new Node(key, value);cache.put(key, node);addToHead(node);++size;if (size > capacity) {node = removeTail();cache.remove(node.key);--size;}}}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}private void addToHead(Node node) {node.next = head.next;node.prev = head;head.next = node;node.next.prev = node;}private Node removeTail() {Node node = tail.prev;removeNode(node);return 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);*/

C++

struct Node {int k;int v;Node* prev;Node* next;Node(): k(0), v(0), prev(nullptr), next(nullptr) {}Node(int key, int val): k(key), v(val), prev(nullptr), next(nullptr) {}
};class LRUCache {
public:LRUCache(int capacity): cap(capacity), size(0) {head = new Node();tail = new Node();head->next = tail;tail->prev = head;}int get(int key) {if (!cache.count(key)) return -1;Node* node = cache[key];moveToHead(node);return node->v;}void put(int key, int value) {if (cache.count(key)) {Node* node = cache[key];node->v = value;moveToHead(node);} else {Node* node = new Node(key, value);cache[key] = node;addToHead(node);++size;if (size > cap) {node = removeTail();cache.erase(node->k);--size;}}}private:unordered_map<int, Node*> cache;Node* head;Node* tail;int cap;int size;void moveToHead(Node* node) {removeNode(node);addToHead(node);}void removeNode(Node* node) {node->prev->next = node->next;node->next->prev = node->prev;}void addToHead(Node* node) {node->next = head->next;node->prev = head;head->next = node;node->next->prev = node;}Node* removeTail() {Node* node = tail->prev;removeNode(node);return 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);*/

Go

type node struct {key, val   intprev, next *node
}type LRUCache struct {capacity   intcache      map[int]*nodehead, tail *node
}func Constructor(capacity int) LRUCache {head := new(node)tail := new(node)head.next = tailtail.prev = headreturn LRUCache{capacity: capacity,cache:    make(map[int]*node, capacity),head:     head,tail:     tail,}
}func (this *LRUCache) Get(key int) int {n, ok := this.cache[key]if !ok {return -1}this.moveToFront(n)return n.val
}func (this *LRUCache) Put(key int, value int) {n, ok := this.cache[key]if ok {n.val = valuethis.moveToFront(n)return}if len(this.cache) == this.capacity {back := this.tail.prevthis.remove(back)delete(this.cache, back.key)}n = &node{key: key, val: value}this.pushFront(n)this.cache[key] = n
}func (this *LRUCache) moveToFront(n *node) {this.remove(n)this.pushFront(n)
}func (this *LRUCache) remove(n *node) {n.prev.next = n.nextn.next.prev = n.prevn.prev = niln.next = nil
}func (this *LRUCache) pushFront(n *node) {n.prev = this.headn.next = this.head.nextthis.head.next.prev = nthis.head.next = n
}

TypeScript

class LRUCache {capacity: number;map: Map<number, number>;constructor(capacity: number) {this.capacity = capacity;this.map = new Map();}get(key: number): number {if (this.map.has(key)) {const val = this.map.get(key)!;this.map.delete(key);this.map.set(key, val);return val;}return -1;}put(key: number, value: number): void {this.map.delete(key);this.map.set(key, value);if (this.map.size > this.capacity) {this.map.delete(this.map.keys().next().value);}}
}/*** 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

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;struct Node {key: i32,value: i32,prev: Option<Rc<RefCell<Node>>>,next: Option<Rc<RefCell<Node>>>,
}impl Node {#[inline]fn new(key: i32, value: i32) -> Self {Self {key,value,prev: None,next: None,}}
}struct LRUCache {capacity: usize,cache: HashMap<i32, Rc<RefCell<Node>>>,head: Option<Rc<RefCell<Node>>>,tail: Option<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 {fn new(capacity: i32) -> Self {Self {capacity: capacity as usize,cache: HashMap::new(),head: None,tail: None,}}fn get(&mut self, key: i32) -> i32 {match self.cache.get(&key) {Some(node) => {let node = Rc::clone(node);self.remove(&node);self.push_front(&node);let value = node.borrow().value;value}None => -1,}}fn put(&mut self, key: i32, value: i32) {match self.cache.get(&key) {Some(node) => {let node = Rc::clone(node);node.borrow_mut().value = value;self.remove(&node);self.push_front(&node);}None => {let node = Rc::new(RefCell::new(Node::new(key, value)));self.cache.insert(key, Rc::clone(&node));self.push_front(&node);if self.cache.len() > self.capacity {let back_key = self.pop_back().unwrap().borrow().key;self.cache.remove(&back_key);}}};}fn push_front(&mut self, node: &Rc<RefCell<Node>>) {match self.head.take() {Some(head) => {head.borrow_mut().prev = Some(Rc::clone(node));node.borrow_mut().prev = None;node.borrow_mut().next = Some(head);self.head = Some(Rc::clone(node));}None => {self.head = Some(Rc::clone(node));self.tail = Some(Rc::clone(node));}};}fn remove(&mut self, node: &Rc<RefCell<Node>>) {match (node.borrow().prev.as_ref(), node.borrow().next.as_ref()) {(None, None) => {self.head = None;self.tail = None;}(None, Some(next)) => {self.head = Some(Rc::clone(next));next.borrow_mut().prev = None;}(Some(prev), None) => {self.tail = Some(Rc::clone(prev));prev.borrow_mut().next = None;}(Some(prev), Some(next)) => {next.borrow_mut().prev = Some(Rc::clone(prev));prev.borrow_mut().next = Some(Rc::clone(next));}};}fn pop_back(&mut self) -> Option<Rc<RefCell<Node>>> {match self.tail.take() {Some(tail) => {self.remove(&tail);Some(tail)}None => None,}}
}

C#

public class LRUCache {class Node {public Node Prev;public Node Next;public int Key;public int Val;}private Node head = new Node();private Node tail = new Node();private Dictionary<int, Node> cache = new Dictionary<int, Node>();private readonly int capacity;private int size;public LRUCache(int capacity) {this.capacity = capacity;head.Next = tail;tail.Prev = head;}public int Get(int key) {Node node;if (cache.TryGetValue(key, out node)) {moveToHead(node);return node.Val;}return -1;}public void Put(int key, int Val) {Node node;if (cache.TryGetValue(key, out node)) {moveToHead(node);node.Val = Val;} else {node = new Node() { Key = key, Val = Val };cache.Add(key, node);addToHead(node);if (++size > capacity) {node = removeTail();cache.Remove(node.Key);--size;}}}private void moveToHead(Node node) {removeNode(node);addToHead(node);}private void removeNode(Node node) {node.Prev.Next = node.Next;node.Next.Prev = node.Prev;}private void addToHead(Node node) {node.Next = head.Next;node.Prev = head;head.Next = node;node.Next.Prev = node;}private Node removeTail() {Node node = tail.Prev;removeNode(node);return 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,Val);*/

Swift

class Node {var key: Intvar val: Intvar prev: Node?var next: Node?init() {self.key = 0self.val = 0}init(_ key: Int, _ val: Int) {self.key = keyself.val = val}
}class LRUCache {private var cache = [Int: Node]()private let head: Nodeprivate let tail: Nodeprivate let capacity: Intprivate var size: Intinit(_ capacity: Int) {self.capacity = capacityself.size = 0self.head = Node()self.tail = Node()head.next = tailtail.prev = head}func get(_ key: Int) -> Int {guard let node = cache[key] else {return -1}moveToHead(node)return node.val}func put(_ key: Int, _ value: Int) {if let node = cache[key] {node.val = valuemoveToHead(node)} else {let newNode = Node(key, value)cache[key] = newNodeaddToHead(newNode)size += 1if size > capacity {let tail = removeTail()cache.removeValue(forKey: tail.key)size -= 1}}}private func moveToHead(_ node: Node) {removeNode(node)addToHead(node)}private func removeNode(_ node: Node) {node.prev?.next = node.nextnode.next?.prev = node.prev}private func addToHead(_ node: Node) {node.next = head.nextnode.prev = headhead.next?.prev = nodehead.next = node}private func removeTail() -> Node {let node = tail.prev!removeNode(node)return node}
}/*** Your LRUCache object will be instantiated and called as such:* let obj = LRUCache(capacity)* let ret_1: Int = obj.get(key)* obj.put(key, value)*/