题目
请你设计并实现一个满足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 <= 3000$
$0 <= key <= 10000$
$0 <= value <= 10^5$
最多调用 $2 * 10^5$ 次get和put
题解1
题目要求实现一个可以存储key-value形式数据的数据结构，并且可以记录最近访问的key值。首先想到的就是用字典来存储key-value结构，这样对于查找操作时间复杂度就是$O(1)$。
但是因为字典本身是无序的，所以我们还需要一个类似于队列的结构来记录访问的先后顺序，这个队列需要支持如下几种操作：
- 在末尾加入一项
- 删除头部一项
- 将队列中某一项移到末尾
所以我们可以想到链表。链表有顺序之分，插入删除快，但是查找慢。
那是用单向链表还是双向链表呢？
对于单向链表，哈希表的结构类似于{key: ListNode(value)}，即键所对应的是一个节点地址，节点的值是value。对于单向链表，可以在常数的时间内找到对应的节点，但是如果想删除节点或者将它移到尾部，则需要从头遍历整个链表，对于这种情况需要的时间复杂度也是$O(n)$。
而对于双向链表，可以在常数时间内在任何位置插入或删除节点，而且可以方便地维护头尾节点的指针。
因此，这道题就用一种新的数据结构：哈希链表。
双向链表可以用来维护缓存中数据的访问顺序，链表头部是最近访问过的数据，链表尾部是最久没有访问过的数据。同时哈希表用来快速查找键对应的链表节点，以及在链表中删除或移动节点。
双向链表可以直接用list<pair<int, int>>表示，它是C++标准库中的一个容器，可以在任何位置进行常数时间的插入和删除。
哈希表直接用unordered_map<int, list<pair<int, int>>::iterator>即可。
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
| class LRUCache {
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (hash_map.find(key) == hash_map.end())
return -1;
auto it = hash_map[key];
link_list.splice(link_list.begin(), link_list, it);
return it->second;
}
void put(int key, int value) {
if (hash_map.find(key) != hash_map.end()) {
auto it = hash_map[key];
it->second = value;
link_list.splice(link_list.begin(), link_list, it);
return;
}
if (link_list.size() == cap) {
auto last = link_list.back();
hash_map.erase(last.first);
link_list.pop_back();
}
link_list.push_front({key, value});
hash_map[key] = link_list.begin();
}
private:
int cap;
list<pair<int, int>> link_list;
unordered_map<int, list<pair<int, int>>::iterator>
hash_map;
};
|
题解2
上面的双向链表是直接用标准库list<pair<int, int>>实现的，当然我们也可以建立Node、实现双链表。
首先定义一个Node结构，然后创建一个头节点和一个尾节点，分别指向链表的第一个和最后一个节点。你还需要定义一些函数来在链表中插入、删除和查找节点。
下面是一个简单的例子：
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
85
86
87
88
89
90
91
92
93
94
95
|
struct Node {
int data;
Node* prev;
Node* next;
Node(int x) : data(x), prev(nullptr), next(nullptr) {}
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
void insertAtHead(int data) {
Node* newNode = new Node(data);
newNode->next = head;
if (head != nullptr) {
head->prev = newNode;
}
head = newNode;
if (tail == nullptr) {
tail = newNode;
}
}
void insertAtTail(int data) {
if (head == nullptr) {
insertAtHead(data);
return;
}
Node* newNode = new Node(data);
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
Node* search(int val) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == val) {
return temp;
}
temp = temp->next;
}
return nullptr;
}
void deleteAll(int val) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == val) {
if (temp == head) {
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
} else if (temp == tail) {
tail = tail->prev;
tail->next = nullptr;
} else {
temp->prev->next =
temp->next;
temp->next->prev =
temp->prev;
}
Node* delNode = temp;
temp = temp->next;
delete delNode;
} else {
temp = temp->next;
}
}
}
void printList() {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
};
|
完整代码如下：
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
85
86
| struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
unordered_map<int, Node*> cache;
Node* head;
Node* tail;
int size;
int capacity;
public:
LRUCache(int capacity) {
this->capacity = capacity;
size = 0;
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.count(key) == 0)
return -1;
Node* node = cache[key];
moveToHead(node);
return node->value;
}
void put(int key, int value) {
if (cache.count(key) == 0) {
Node* node = new Node(key, value);
cache[key] = node;
addToHead(node);
++size;
if (size > capacity) {
Node* removed = removeTail();
cache.erase(removed->key);
delete removed;
--size;
}
} else {
Node* node = cache[key];
node->value = value;
moveToHead(node);
}
}
private:
void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(Node* node) {
removeNode(node);
addToHead(node);
}
Node* removeTail() {
Node* node = tail->prev;
removeNode(node);
return node;
}
};
|
