原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

• LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
• int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
• void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

样例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 lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3

Tag

双向链表 set 哈希映射

题目分析

这题是LeetCode 146. LRU 缓存-CSDN博客的升级版，加入了使用次数判断，如果只用一个双向链表的话无法满足需求，需要根据使用频率cnt来维护多个双向链表。

思路

数据结构：

1.链表节点

记录value值，有指向前节点和后节点的指针

2.双向链表

有链表头尾节点，借助头结点可以将新加入的节点O(1)复杂度加入队首，借助尾节点可以O(1)复杂度去除最久未使用的节点（即尾节点prev指向的节点）。

用哈希表unordered_map<int,node*> mp维护关键字到链表节点地址的映射，确保可以在O(1)复杂度时间根据关键字找到节点

3.LFUCache类

哈希表list_ptr维护多条双向链表，根据关键字使用频率找到所存储的链表位置，并进行相应操作

哈希表cnt记录关键字出现的次数

红黑树min_cnt记录当前存在的频率最低的关键字有哪些（即找到cnt最低的那条双向链表）

实现方法

1.get查询

找到了将关键字所在节点node从当前频率的链表中删掉，放到当前频率+1的链表首部，同时更新cnt修改关键字出现的次数，若当前频率+1还有链表需要申请并用list_ptr记录

2.put操作

修改频率和get一样，不同的是需要判断是否找过缓存，如果超过根据min_cnt先找到频率最低的那条链表，再删掉链表的尾节点，同时注意更新min_cnt、cnt和list_ptr

3.注意

删除节点后需要判断链表是否为空，若为空则需要删除这条链表，并且删掉min_cnt中的记录和list_ptr中记录当前链表的地址

C++代码

class node{
public:node *prev,*next;int key;int value;node(node *prev,node *next,int key,int value){this->key = key;this->value = value;this->prev = prev;this->next = next;}};class DoublyLinkedList{
public:node *head,*tail;unordered_map<int,node*> mp;//key:关键字 value:存储链表中某个节点地址DoublyLinkedList(){head = new node(nullptr,nullptr,0,0);tail = new node(head,nullptr,0,0);head->next = tail;}//将node移动到队首void adjust(node* temp) {temp->next = head->next;temp->prev = head;head->next = temp;temp->next->prev = temp;}//删除节点void remove(node *move){move->prev->next = move->next;move->next->prev = move->prev;}//删除尾节点int remove_tail(){node* del = tail->prev;int key = del->key;tail->prev = del->prev;del->prev->next = tail;mp.erase(key);return key;}
};class LFUCache {
public:int capacity;int now;unordered_map<int,DoublyLinkedList*> list_ptr;//key:使用次数 value:双向链表地址unordered_map<int,int>cnt;//key:关键字 value:出现次数set<int>min_cnt;//查找出现次数最少的LFUCache(int capacity) {this->capacity = capacity;now = 0;}int get(int key) {if(cnt.count(key)){int count = cnt[key];//关键字查询前出现次数cnt[key]++;//查询后访问次数+1DoublyLinkedList *list = list_ptr[count];//cout<<"size:"<<min_cnt.size()<<endl;int value = list->mp[key]->value;//查询到的值//从count中删除尾节点node* move = list->mp[key];list->remove(move);if(list->head->next == list->tail){//删空了list_ptr.erase(count);min_cnt.erase(count);}//加入count+1中的队首if(list_ptr.count(count+1)){DoublyLinkedList *newlist = list_ptr[count+1];newlist->adjust(move);newlist->mp[key] = move;}else{DoublyLinkedList* newlist = new DoublyLinkedList();list_ptr[count+1] = newlist;newlist->adjust(move);newlist->mp[key] = move;min_cnt.insert(count+1);}return value;}return -1;}void put(int key, int value) {if(cnt.count(key)){int count = cnt[key];//关键字查询前出现次数cnt[key]++;//put后访问次数+1DoublyLinkedList *list = list_ptr[count];list->mp[key]->value = value;//改值//从count中删除尾节点node* move = list->mp[key];list->remove(move);if(list->head->next == list->tail){//删空了list_ptr.erase(count);min_cnt.erase(count);}//加入count+1中的队首if(list_ptr.count(count+1)){DoublyLinkedList *list = list_ptr[count+1];list->adjust(move);list->mp[key] = move;}else{DoublyLinkedList* newlist = new DoublyLinkedList();list_ptr[count+1] = newlist;newlist->adjust(move);newlist->mp[key] = move;min_cnt.insert(count+1);}}else{//加入count = 1的队首if(now+1>capacity){//若超缓存则删除now--;int x = *min_cnt.begin();DoublyLinkedList *list = list_ptr[x];//出现次数最少的那条链表int toRemoveKey = list->remove_tail();cnt.erase(toRemoveKey);//key不在缓存中了,出现次数置0if(list->head->next == list->tail){min_cnt.erase(x);list_ptr.erase(x);}}node* newnode = new node(nullptr,nullptr,key,value);if(list_ptr.count(1)){DoublyLinkedList *list = list_ptr[1];list->adjust(newnode);list->mp[key] = newnode;}else{DoublyLinkedList* newlist = new DoublyLinkedList();newlist->adjust(newnode);newlist->mp[key] = newnode;list_ptr[1] = newlist;min_cnt.insert(1);}cnt[key] = 1;now++;}}
};