题目内容
实现一个 LFUCache 类，三个接口：
-
LFUCache(int capacity) 创建一个大小为 capacity 的缓存
-
get(int key) 从缓存中获取键为 key 的键值对的 value
-
put(int key, int value) 向缓存中添加键值对 (key, value)
要求 get 和 put 的均摊时间复杂度为
O
(
1
)
O(1)
O(1)
题解
对于 get 操作，我们需要快速获取到 key 对应的键值对，哈希表可以解决。
对于 put 操作，我们需要快速 put 一个键值对，也可以用哈希表解决。
但是问题在于，我们 get 和 put 时，需要维护每个键的使用次数。
LRU 的实现只需要将每个当前使用的键值对移到链表头，当前使用的键值对在下一次操作前必然是最近最少使用的。
而 LFU 并非如此，当前一个键值对的使用只会增加当前操作的键的使用次数。
所以对于 LFU ，我们需要对每个使用次数都维护一个 LRU 。然后按使用次数从小到大维护一个链表。
相当于外部是一个单调递增的链表，每个链表结点是一个 LRUCache 。
如此
- 需要用哈希表
key2LRUNode 来维护 key 到 LRUNode
- 需要用哈希表
cnt2IncNode 来维护使用次数 cnt 到 IncNode
key2LRUNode 是为了快速找到一个 key 对应的结点
cnt2IncNode 是为了根据使用次数快速找到其对应的结点，从而方便更新一个 LRUNode 的使用次数。
LRUNode 操作的定义
struct LRUNode {
LRUNode* prev;
LRUNode* next;
int key;
int val;
int cnt;
LRUNode(int key, int val): key(key), val(val), prev(nullptr), next(nullptr) {}
};
void removeLRUNodeFromLinklist(LRUNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insertLRUNodeToLinklist(LRUNode* node, LRUNode* head) {
node->next = head->next;
head->next->prev = node;
head->next = node;
node->prev = head;
}
LRUCache 操作的定义
class LRUCache {
void removeLRUNodeFromHashTable(LRUNode* node) {
if (!key2LRUNode.count(node->key)) return;
key2LRUNode.erase(node->key);
}
void insertLRUNodeToHashTable(LRUNode* node) {
key2LRUNode[node->key] = node;
}
public:
LRUCache() {
size_ = 0;
head = new LRUNode(-1, -1);
tail = new LRUNode(-2, -1);
head->next = tail;
head->prev = tail;
tail->next = head;
tail->prev = head;
}
void put(int key, int value) {
if (!key2LRUNode.count(key)) {
LRUNode* newLRUNode = new LRUNode(key, value);
insertLRUNodeToLinklist(newLRUNode, head);
insertLRUNodeToHashTable(newLRUNode);
size_ += 1;
} else {
LRUNode* node = key2LRUNode[key];
node->val = value;
removeLRUNodeFromLinklist(node);
insertLRUNodeToLinklist(node, head);
insertLRUNodeToHashTable(node);
}
}
void del(int key) {
if (!key2LRUNode.count(key)) return;
auto node = key2LRUNode[key];
removeLRUNodeFromLinklist(node);
removeLRUNodeFromHashTable(node);
size_ -= 1;
}
LRUNode* pop() {
if (empty()) return nullptr;
LRUNode* node = tail->prev;
del(node->key);
return node;
}
bool empty() const {
return size_ == 0;
}
private:
int size_;
unordered_map<int, LRUNode*> key2LRUNode;
LRUNode* head;
LRUNode* tail;
};
IncNode 的实现
struct IncNode {
int key; // key, 对应的次数
IncNode* prev;
IncNode* next;
LRUCache* lru;
IncNode(int key): key(key), prev(nullptr), next(nullptr), lru(new LRUCache()) {}
};
void removeIncNodeFromLinklist(IncNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insertIncNodeFromLinklist(IncNode* node, IncNode* head) {
node->next = head->next;
head->next->prev = node;
head->next = node;
node->prev = head;
}
LFUCache 的 get 实现
int get(int key) {
// 如果不存在当前 key ，直接返回 -1
if (!key2LRUNode.count(key)) return -1;
// 找到 key 对应的 LRUNode，value 就是 node->val
LRUNode* node = key2LRUNode[key];
int ans = node->val;
// 找到 LRUNode 对应的 IncNode
IncNode* cur = cnt2IncNode[node->cnt];
// 为插入 node 到新的一层的前一个节点做准备
IncNode* pre = cur->prev;
LRUCache* lru = cur->lru;
// 将 LRUNode 从 IncNode 对应的 lru 中移除
lru->del(node->key);
if (lru->empty()) {
// 如果 lru 为空，将 cur 这个 IncNode 移除
removeIncNodeFromHashTable(cur);
removeIncNodeFromLinklist(cur);
} else {
// 如果 cur 对应的 lru 移除 node 后不为空，则 node 新到的计数 IncNode 的前一个就是 cur
pre = cur;
}
// 添加到新的 lru 中
node->cnt += 1;
IncNode* incNode;
// 如果新的 lru 不存在，就创建
if (!cnt2IncNode.count(node->cnt)) {
incNode = new IncNode(node->cnt);
incNode->lru->put(node->key, node->val);
insertIncNodeFromLinklist(incNode, pre);
} else {
incNode = cnt2IncNode[node->cnt];
incNode->lru->put(node->key, node->val);
}
insertIncNodeToHashTable(incNode);
return ans;
}
LFUCache 的 put 实现
void put(int key, int value) {
if (!key2LRUNode.count(key)) {
if (size_ >= capacity_) {
IncNode* incNode = head->next;
LRUNode* lruNode = incNode->lru->pop();
removeLRUNodeFromHashTable(lruNode);
size_ -= 1;
}
LRUNode* node = new LRUNode(key, value);
// 如果新的 lru 不存在，就创建
IncNode* incNode;
// 不存在计数为 1 的 IncNode，创建
if (!cnt2IncNode.count(node->cnt)) {
incNode = new IncNode(node->cnt);
incNode->lru->put(node->key, node->val);
// 将这个 IncNode 添加到 IncNode 对应的链表中
insertIncNodeFromLinklist(incNode, head);
} else {
incNode = cnt2IncNode[node->cnt];
incNode->lru->put(node->key, node->val);
}
insertIncNodeToHashTable(incNode);
insertLRUNodeToHashTable(node);
size_ += 1;
} else {
LRUNode* node = key2LRUNode[key];
node->val = value;
IncNode* cur = cnt2IncNode[node->cnt];
IncNode* pre = cur->prev;
LRUCache* lru = cur->lru;
// 从当前 lru 中删除
lru->del(node->key);
// 如果 lru 为空，说明要合并了，先找到前后的两个
if (lru->empty()) {
removeIncNodeFromHashTable(cur);
removeIncNodeFromLinklist(cur);
} else {
pre = cur;
}
IncNode* incNode;
// 添加到新的 lru 中
node->cnt += 1;
// 如果新的 lru 不存在，就创建
if (!cnt2IncNode.count(node->cnt)) {
incNode = new IncNode(node->cnt);
incNode->lru->put(node->key, node->val);
insertIncNodeFromLinklist(incNode, pre);
cnt2IncNode[node->cnt] = incNode;
} else {
incNode = cnt2IncNode[node->cnt];
incNode->lru->put(node->key, node->val);
}
insertIncNodeToHashTable(incNode);
insertLRUNodeToHashTable(node);
}
}
