当前位置：网站首页>Leetcode（146）——LRU 缓存
Leetcode（146）——LRU 缓存
2022-06-24 19:03:00 【SmileGuy17】
Leetcode（146）——LRU 缓存
题目
请你设计并实现一个满足 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 ) O(1) 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 1 1 <= capacity <= 3000 3000 3000
- 0 0 0 <= key <= 10000 10000 10000
- 0 0 0 <= value <= 1 0 5 10^5 105
- 最多调用 2 ∗ 1 0 5 2 * 10^5 2∗105 次 get 和 put
题解
方法一：哈希表+双向链表
思路
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O ( 1 ) O(1) O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
- 对于 get 操作，首先判断 key 是否存在：
- 如果 key 不存在，则返回 − 1 -1 −1；
- 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
- 对于 put 操作，首先判断 key 是否存在：
- 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
上述各项操作中，访问哈希表的时间复杂度为 O ( 1 ) O(1) O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O ( 1 ) O(1) O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O ( 1 ) O(1) O(1) 时间内完成。
数据结构的使用原因
- 为什么不用单链表？因为如果在 get 操作访问的是一个处于链表中间位置的节点时，使用双向链表可以快速获取其前一个节点和后一个节点的地址，并使其相连。
- 为什么双向链表还要存储 key？因为在插入新值时，如果链表长度等于 capacity ，则要删除哈希表中的键值对，此时就需要获取最长未使用的键值来调用
erase函数。 - 哈希表的结构为
unordered_map<int, ListNode*>，以作到快速查找到对应的 key-value ，同时因为存储的是ListNode*，所以可以重新对链表进行更新。
小贴士
在双向链表的实现中，使用一个 伪头部（dummy head） 和 伪尾部（dummy tail） 标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
代码实现
我自己的：
class LRUCache {
// 双向链表存储使用情况
typedef struct dataUse{
// 双向链表存一组 key-value，因为在超出capacity要删除hashmap里key-value pair 时。
// 必须要通过Node里的key来删除，hashmap无法通过value来删除
int key;
int value;
// 当get操作时候需要访问使用情况在中间的元素时，需要其前一个和后一个元素以方便重新连接
struct dataUse *next;
struct dataUse *last;
dataUse():key(-1), value(-1), next(nullptr), last(nullptr){
}
dataUse(int k, int v, struct dataUse *nextone, struct dataUse *lastone):
key(k), value(v), next(nextone), last(lastone){
}
}DU;
// 哈希表保存其对应在链表中的地址
unordered_map<int, DU*> cache;
DU *h, *t; // 头结点和尾结点，其中 h->next 则表示最晚未使用的关键字
int maxsize;
void movetoT(DU *p){
p->last->next = p->next;
p->next->last = p->last;
p->last = t->last;
p->next = t;
t->last->next = p;
t->last = p;
}
void addtoT(int key, int value){
t->last->next = new DU(key, value, t, t->last);
t->last = t->last->next;
}
public:
LRUCache(int capacity):h(new DU), t(new DU), maxsize(capacity){
h->next = t;
t->last = h;
}
int get(int key) {
if(cache.count(key) == 0) return -1;
else{
if(t->last != cache[key]) movetoT(cache[key]);
return cache[key]->value;
}
}
void put(int key, int value) {
if(cache.count(key) == 0){
if(cache.size() == maxsize){
cache.erase(h->next->key); // 删除掉哈希表中太久未使用的关键对
cache.emplace(key, h->next);
cache[key]->key = key;
cache[key]->value = value;
movetoT(cache[key]);
}else{
addtoT(key, value);
cache.emplace(key, t->last);
}
}else{
if(t->last != cache[key]) movetoT(cache[key]);
cache[key]->value = value;
}
}
};
/** * 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); */
Leetcode 官方题解：
struct DLinkedNode {
int key, value;
DLinkedNode* prev;
DLinkedNode* next;
DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {
}
DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {
}
};
class LRUCache {
private:
unordered_map<int, DLinkedNode*> cache;
DLinkedNode* head;
DLinkedNode* tail;
int size;
int capacity;
public:
LRUCache(int _capacity): capacity(_capacity), size(0) {
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (!cache.count(key)) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
DLinkedNode* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (!cache.count(key)) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode* node = new DLinkedNode(key, value);
// 添加进哈希表
cache[key] = node;
// 添加至双向链表的头部
addToHead(node);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode* removed = removeTail();
// 删除哈希表中对应的项
cache.erase(removed->key);
// 防止内存泄漏
delete removed;
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
DLinkedNode* node = cache[key];
node->value = value;
moveToHead(node);
}
}
void addToHead(DLinkedNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(DLinkedNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(DLinkedNode* node) {
removeNode(node);
addToHead(node);
}
DLinkedNode* removeTail() {
DLinkedNode* node = tail->prev;
removeNode(node);
return node;
}
};
网友题解：
struct lrunode{
int val;
int key;
lrunode* next;
lrunode* last;
};
class LRUCache {
public:
lrunode* mp[10001];
lrunode *list,*tail;
int capacity;
int size;
LRUCache(int capacity) {
for(int i=0;i<10001;++i)mp[i] = nullptr;
this->capacity = capacity;
list = tail = nullptr;
size = 0;
}
int get(int key) {
if(mp[key]!=nullptr){
lrunode* t = mp[key];
used(t);
return t->val;
}
else return -1;
}
void put(int key, int value) {
if(mp[key]!=nullptr){
lrunode* t = mp[key];
t->val = value;
used(t);
}else{
lrunode* node = new lrunode;
node->key = key;
node->val = value;
mp[key] = node;
push_front(node);
if(size<capacity){
size++;
}else{
pop_back();
}
}
}
void used(lrunode* t){
if(t==list)return;
if(t->last)t->last->next = t->next;
if(t->next)t->next->last = t->last;
else tail = t->last;
t->last = nullptr;
t->next = list;
if(list)list->last = t;
list = t;
if(tail == nullptr)tail = t;
}
void push_front(lrunode* node){
node->last = nullptr;
node->next = list;
if(list)list->last = node;
list = node;
if(tail == nullptr)tail = node;
}
void pop_back(){
lrunode* t = tail;
if(list == tail){
list = tail = nullptr;
}else{
tail = tail->last;
tail->next = nullptr;
}
mp[t->key] = nullptr;
delete t;
}
};
复杂度分析
时间复杂度：对于 put 和 get 都是 O ( 1 ) O(1) O(1)。
空间复杂度： O ( c a p a c i t y ) O(capacity) O(capacity)，因为哈希表和双向链表最多存储 2 ∗ capacity + 2 2*\text{capacity} + 2 2∗capacity+2 个元素。
边栏推荐
- Dongyuhui is not enough to bring goods to "rescue" live broadcast
- Ribbon源码分析之@LoadBalanced与LoadBalancerClient
- Predicate
- 2022年最新四川建筑八大员（电气施工员）模拟题库及答案
- [cann document express issue 05] let you know what operators are
- 华为云ModelArts第四次蝉联中国机器学习公有云服务市场第一！
- 消息称腾讯正式宣布成立“XR”部门，押注元宇宙;谷歌前 CEO：美国即将输掉芯片竞争，要让台积电、三星建更多工厂...
- Instruction rearrangement concept
- Bytebase joins Alibaba cloud polardb open source database community
- 苹果、微软、谷歌不再掐架，今年要合力干一件大事
猜你喜欢
Using dynamic time warping (DTW) to solve the similarity measurement of time series and the similarity identification analysis of pollution concentration in upstream and downstream rivers
Bytebase joins Alibaba cloud polardb open source database community
Apple, Microsoft and Google will no longer fight each other. They will work together to do a big thing this year
Where are Xiaomi mobile phone's favorite SMS and how to delete them
Teach you how to view the number of connected people on WiFi in detail how to view the number of connected people on WiFi
What is CNN (convolutional neural network)
使用gorm查询数据库时reflect: reflect.flag.mustBeAssignable using unaddressable value
顺序栈1.0版本
Microsoft Office Excel 2013 2016 graphic tutorial on how to enable macro function
微信小程序自定义tabBar
随机推荐
[cloud resident co creation] ModelBox draws your own painting across the air
The largest DPU manufacturer in history (Part 1)
Coinbase将推出首个针对个人投资者的加密衍生产品
微信小程序自定义tabBar
Get to know the data structure of redis - hash
物聯網？快來看 Arduino 上雲啦
Some ideas about chaos Engineering
Todesk remote control, detailed introduction and tutorial
Two fellow countrymen from Hunan have jointly launched a 10 billion yuan IPO
Predicate
Coinbase will launch the first encryption derivative for individual investors
【CANN文档速递06期】初识TBE DSL算子开发
Database index can improve query efficiency. Ask what will improve, what is the difference between inapplicable index and index use, and what will happen.
顺序栈1.0版本
Docker installing MySQL
Bytebase 加入阿裏雲 PolarDB 開源數據庫社區
苹果不差钱，但做内容“没底气”
Error in Android connection database query statement
物联网？快来看 Arduino 上云啦
Behind Tiantian Jianbao storm: tens of millions in arrears, APP shutdown, and the founder's premeditated plan to run away?