146.LRU 缓存

【LetMeFly】146.LRU 缓存:双向链表 + 哈希

力扣题目链接:https://leetcode.cn/problems/lru-cache/

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 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 <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105getput

方法一:双向链表 + 哈希

使用一个双向链表来作为LRU缓存。越靠近链表头部的节点使用时间越近。

使用一个哈希表,来实现从key映射到节点的功能。

为了能从节点映射到哈希表的键值key,在节点中也额外存储一份这个节点的key值:

1
2
3
4
5
class LRU_Node {
public:
LRU_Node* previous, *next;
int key, value;
}

为了方便操作,可以在双向链表的首尾各添加一个空节点,以避免“是否为空”的特判。

对于get操作:

若哈希表中存有该key,则由哈希表映射出该节点,将该节点移动为链表的第一个节点,并返回节点的value

若哈希表中不存在该key,直接返回-1

对于put操作:

若哈希表中存有该key,则由哈希表映射出该节点,更新该节点的值,并将该节点移动为链表的第一个节点。

若哈希表中不存在该key,创建该节点并将其置于链表的第一个节点。若哈希表的容量大于最大容量,则由tail.previous得到最后一个节点,在哈希表中删除这个节点的key,并在链表中删除这个节点。

  • 时间复杂度:每次操作的时间复杂度都是$O(1)$
  • 空间复杂度$O(max(put, capacity))$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class LRU_Node {
public:
LRU_Node* previous, *next;
int key, value;
LRU_Node(LRU_Node* previous, LRU_Node* next, int key, int value) {
this->previous = previous;
this->next = next;
this->key = key;
this->value = value;
}
};

class LRUCache {
private:
LRU_Node* head, *tail;
int capacity;
unordered_map<int, LRU_Node*> ma;

void refresh(int key, int value) {
LRU_Node* thisNode = ma[key];
thisNode->value = value;

LRU_Node* previous = thisNode->previous, *next = thisNode->next;
previous->next = next, next->previous = previous;

thisNode->next = head->next;
head->next = thisNode;
thisNode->previous = head;
thisNode->next->previous = thisNode;
}
public:
LRUCache(int capacity) {
head = new LRU_Node(nullptr, nullptr, 0, 0);
tail = new LRU_Node(head, nullptr, 0, 0);
head->next = tail;
this->capacity = capacity;
}

int get(int key) {
if (ma.count(key)) {
refresh(key, ma[key]->value);
return ma[key]->value;
}
return -1;
}

void put(int key, int value) {
if (ma.count(key)) {
refresh(key, value);
return;
}
LRU_Node* thisNode = new LRU_Node(head, head->next, key, value);
ma[key] = thisNode;
head->next = thisNode, thisNode->next->previous = thisNode;
if (ma.size() > capacity) {
LRU_Node* toRemove = tail->previous;
ma.erase(toRemove->key);
toRemove->previous->next = tail;
tail->previous = toRemove->previous;
}
}

void debug() {
cout << "Now size: " << ma.size() << ": [";
LRU_Node* p = head->next;
while (p != tail) {
if (p != head->next) {
cout << ", ";
}
cout << "(" << p->key << "|" << p->value << ")";
p = p->next;
}
cout << "] | [";
p = tail->previous;
while (p != head) {
if (p != tail->previous) {
cout << ", ";
}
cout << "(" << p->key << "|" << p->value << ")";
p = p->previous;
}
cout << "]" << endl;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class LRU_Node:

def __init__(self, previous, next, key, value):
self.previous = previous
self.next = next
self.key = key
self.value = value


class LRUCache:

def __init__(self, capacity: int):
self.capacity = capacity
self.head = LRU_Node(None, None, 0, 0)
self.tail = LRU_Node(self.head, None, 0, 0)
self.head.next = self.tail
self.ma = dict()


def move2first(self, thisNode: LRU_Node):
thisNode.previous.next = thisNode.next
thisNode.next.previous = thisNode.previous

thisNode.previous = self.head
thisNode.next = self.head.next
self.head.next = thisNode
thisNode.next.previous = thisNode


def get(self, key: int) -> int:
if key in self.ma:
self.move2first(self.ma[key])
return self.ma[key].value
return -1


def put(self, key: int, value: int) -> None:
if key in self.ma:
thisNode = self.ma[key]
thisNode.value = value
self.move2first(thisNode)
else:
thisNode = LRU_Node(self.head, self.head.next, key, value)
self.ma[key] = thisNode
self.head.next = thisNode
thisNode.next.previous = thisNode
if len(self.ma) > self.capacity:
toRemove = self.tail.previous
del self.ma[toRemove.key]
toRemove.previous.next = self.tail
self.tail.previous = toRemove.previous

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/133241877


146.LRU 缓存
https://blog.letmefly.xyz/2023/09/24/LeetCode 0146.LRU缓存/
作者
Tisfy
发布于
2023年9月24日
许可协议