请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
函数 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
提示:
LRU 缓存机制可以通过哈希表辅以双向链表实现,我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 O ( 1 ) O(1) O(1) 的时间内完成 get 或者 put 操作。具体的方法如下:
上述各项操作中,访问哈希表的时间复杂度为 O ( 1 ) O(1) O(1),在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O ( 1 ) O(1) O(1)。而将一个节点移到双向链表的头部,可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作,都可以在 O ( 1 ) O(1) O(1) 时间内完成。
数据结构的使用原因
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 个元素。