leetcode 链接：LFU 缓存
题目
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
实现 LFUCache 类：
LFUCache(int capacity)- 用数据结构的容量capacity初始化对象int get(int key)- 如果键存在于缓存中，则获取键的值，否则返回 -1。void put(int key, int value)- 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
进阶：你可以为这两种操作设计时间复杂度为 O(1) 的实现吗？
示例：
输入：["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]输出：[null, null, null, 1, null, -1, 3, null, -1, 3, 4]解释：// cnt(x) = 键 x 的使用计数// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）LFUCache lFUCache = new LFUCache(2);lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1lFUCache.get(1); // 返回 1// cache=[1,2], cnt(2)=1, cnt(1)=2lFUCache.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小// cache=[3,1], cnt(3)=1, cnt(1)=2lFUCache.get(2); // 返回 -1（未找到）lFUCache.get(3); // 返回 3// cache=[3,1], cnt(3)=2, cnt(1)=2lFUCache.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用// cache=[4,3], cnt(4)=1, cnt(3)=2lFUCache.get(1); // 返回 -1（未找到）lFUCache.get(3); // 返回 3// cache=[3,4], cnt(4)=1, cnt(3)=3lFUCache.get(4); // 返回 4// cache=[3,4], cnt(4)=2, cnt(3)=3
解答 & 代码
LFUCache 构造如下图所示，包含
- 一个哈希 Map，存储
- capacity 容量
- 两层链表（可以想象为类似哈希表的构造）
- 外层链表的节点代表各个频度，从头节点到尾节点频度递减
- 外层链表的每个频度又对应一个链表，代表该频度的节点链表，从头节点到尾节点由新到旧
class FreqNode; // 前向声明
class Node { // 节点类
public:
int key; // 键
int val; // 值
Node* pre; // 指向前一节点（更靠后被使用/更新）的指针
Node* next; // 指向后一节点（更靠前被使用/更旧）的指针
FreqNode* freqNode; // 对应频度的频度节点指针
Node()
{
pre = nullptr;
next = nullptr;
freqNode = nullptr;
}
Node(int key, int val)
{
this->key = key;
this->val = val;
pre = nullptr;
next = nullptr;
freqNode = nullptr;
}
};
class FreqNode { // 频度链表节点类
public:
int freq; // 频度
Node* preHead; // 该频度的节点链表的虚拟头节点
Node* afterEnd; // 该频度的节点链表的虚拟尾节点
FreqNode* pre; // 指向前一个（更大频度）的频度节点的指针
FreqNode* next; // 指向后一个（更小频度）的频度节点的指针
FreqNode(int freq)
{
this->freq = freq;
preHead = new Node(-1, -1);
afterEnd = new Node(-1, -1);
preHead->next = afterEnd;
afterEnd->pre = preHead;
}
void removeNode(Node* node) // 从 node 节点所在频度的链表中移除该节点，但不 delete 该节点
{
if(isEmpty())
return;
node->pre->next = node->next;
node->next->pre = node->pre;
}
void deleteNode(Node* node) // 从 node 节点所在频度的链表中删除该节点（delete 该节点）
{
if(isEmpty())
return;
node->pre->next = node->next;
node->next->pre = node->pre;
delete node;
}
void insertNode(Node* node) // 前插，将 node 节点插入当前频度对应链表的头部（虚拟头节点之后）
{
Node* next = preHead->next;
preHead->next = node;
node->pre = preHead;
node->next = next;
next->pre = node;
node->freqNode = this;
}
bool isEmpty() // 判断当前频度的节点链表是否为空
{
return preHead->next == afterEnd;
}
};
class LFUCache {
private:
unordered_map<int, Node*> map; // 哈希表，存储 key 和 node 的键值对
FreqNode* dummyHead; // 频度链表（外层链表）的虚拟头节点
FreqNode* dummyEnd; // 频度链表（外层链表）的虚拟尾节点
int capacity; // 容量
bool isEmpty() // 频度链表（外层链表）是否为空
{
return dummyHead->next == dummyEnd;
}
void deleteFreqNode(FreqNode* freqNode) // 从外层链表删除频度节点 freqNode
{
if(isEmpty())
return;
freqNode->pre->next = freqNode->next;
freqNode->next->pre = freqNode->pre;
delete freqNode;
}
void freqInc(Node* node) // 将 node 移动到 频度+1 的频度链表
{
FreqNode* freqList = node->freqNode;
freqList->removeNode(node);
int freq = freqList->freq;
FreqNode* preFreqList = freqList->pre;
if(freqList->isEmpty())
deleteFreqNode(freqList);
if(preFreqList->freq != freq + 1)
{
FreqNode* newFreqList = new FreqNode(freq + 1);
newFreqList->pre = preFreqList;
newFreqList->next = preFreqList->next;
preFreqList->next->pre = newFreqList;
preFreqList->next = newFreqList;
preFreqList = newFreqList;
}
preFreqList->insertNode(node);
}
void insertFreqNode(FreqNode* freqNode) // 尾插，在外层链表中插入一个新的频度
{
freqNode->pre = dummyEnd->pre;
freqNode->next = dummyEnd;
dummyEnd->pre->next = freqNode;
dummyEnd->pre = freqNode;
}
public:
LFUCache(int capacity) {
this->capacity = capacity;
dummyHead = new FreqNode(-1);
dummyEnd = new FreqNode(-1);
dummyHead->next = dummyEnd;
dummyEnd->pre = dummyHead;
}
int get(int key) {
// 如果键不存在于缓存中，返回 -1
if(map.find(key) == map.end())
return -1;
// 如果键存在于缓存中，返回键的值
else
{
Node* node = map[key];
freqInc(node);
return node->val;
}
}
void put(int key, int value) {
if(capacity == 0) // 注意特殊情况，容量可能为 0，则不操作
return;
// 如果键不存在
if(map.find(key) == map.end())
{
// 如果缓存容量已满，先删除最近最久未使用的节点（频度最小的（外层最右段）频度链表中的尾节点）
if(map.size() == capacity)
{
FreqNode* minFreqList = dummyEnd->pre;
Node* deleteNode = minFreqList->afterEnd->pre;
map.erase(deleteNode->key);
minFreqList->deleteNode(deleteNode);
if(minFreqList->isEmpty())
deleteFreqNode(minFreqList);
}
// 插入新节点
Node* newNode = new Node(key, value);
map[key] = newNode;
FreqNode* freqList = dummyEnd->pre;
if(freqList->freq != 1)
{
FreqNode* newFreqList = new FreqNode(1);
insertFreqNode(newFreqList);
freqList = newFreqList;
}
freqList->insertNode(newNode);
}
// 如果键存在，更新键对应的值，频度+1
else
{
Node* node = map[key];
node->val = value;
freqInc(node);
}
}
};
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache* obj = new LFUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
执行结果：
执行结果：通过
执行用时：380 ms, 在所有 C++ 提交中击败了 24.71% 的用户
内存消耗：173 MB, 在所有 C++ 提交中击败了 19.54% 的用户
若有收获，就点个赞吧
0 人点赞
