Design and implement a data structure for Least Frequently Used (LFU) cache .
Implement the LFUCache class:
LFUCache(int capacity) Initializes the object with the capacity of the data structure.int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1 .void put(int key, int value) Sets or inserts the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be evicted.Notice that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.
Follow up: Could you do both operations in O ( 1 ) O(1) O(1) time complexity?
Example 1:
Input ["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]] Output [null, null, null, 1, null, -1, 3, null, -1, 3, 4] Explanation LFUCache lFUCache = new LFUCache(2); lFUCache.put(1, 1); lFUCache.put(2, 2); lFUCache.get(1); // return 1 lFUCache.put(3, 3); // evicts key 2 lFUCache.get(2); // return -1 (not found) lFUCache.get(3); // return 3 lFUCache.put(4, 4); // evicts key 1. lFUCache.get(1); // return -1 (not found) lFUCache.get(3); // return 3 lFUCache.get(4); // return 4Constraints:
0 <= capacity, key, value <= 104At most 105 calls will be made to get and put.题意：为最不经常使用 LFU 缓存算法设计并实现数据结构 LFUCache 类：
LFUCache(int capacity) 用数据结构的容量 capacity 初始化对象int get(int key) 如果键存在于缓存中，则获取键的值，否则返回 -1 。void put(int key, int value) 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效( LFU ) 。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键( LRU ) 。注意：「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
这一题是之前做过的 LRU Cache 的扩展，尽管都会使用哈希映射和双向链表，但是本题更加复杂——需要使用一个哈希映射和一个二维双向链表；哈希映射记录 key 到双向链表结点指针的键值对；一级链表维护 LFU ，按照频次排序；二级链表维护一个 LRU ，每一条二级链表代表具有相同使用次数的缓存；put, get 时更新结点的使用频次、最近是否使用的性质。具体代码如下，比较长：
struct FreqNode; //结构体前向声明 struct DataNode { //数据双向链表结点 int key, val; //key:val int freq = 1; //使用次数,以便实现LFU;通过二级链表中的顺序实现LRU DataNode *prev, *next; //前后指针 FreqNode *freqList; //数据结点所在的频率结点 DataNode(int k = 0, int v = 0, DataNode *p = nullptr, DataNode *n = nullptr, FreqNode *f = nullptr) : key(k), val(v), prev(p), next(n), freqList(f) {} }; struct FreqNode { //频率双向链表结点 int freq; //这一条数据结点双向链表的频率 FreqNode *prior, *after; //前后指针 DataNode *head, *tail; //管理数据结点双向链表的头尾 FreqNode(int freq = 0) { this->freq = freq; head = new DataNode(); tail = new DataNode(); head->next = tail; tail->prev = head; } ~FreqNode() { delete head; delete tail; } void removeDataNode(DataNode *node) { //当某一数据结点被使用,就会从链表中移除 node->prev->next = node->next; //插入到更高使用频率的频率结点管理的数据结点双向链表的表头 node->next->prev = node->prev; } void addDataNodeFirst(DataNode *node) { //最近使用的结点放到数据双向链表表头 node->next = head->next; head->next->prev = node; node->prev = head; head->next = node; node->freqList = this; } }; class LFUCache { private: unordered_map<int, DataNode*> cache; //记录key:数据结点指针的键值对 FreqNode *DHead, *DTail; //频率结点双向链表的头指针,尾指针 int _capacity; void freqInc(DataNode* node) { //将node从原freq对应的数据结点双向链表中移除,如果链表空了则删除链表 FreqNode *linkedlist = node->freqList; FreqNode *preList = linkedlist->prior; linkedlist->removeDataNode(node); //移除node if (linkedlist->head->next == linkedlist->tail) //该链表已经为空,则删除掉它 removeFreqNode(linkedlist); //以使得DTail->prior始终非空,方便移除最不经常使用的、最近最少使用的结点 ++node->freq; //将node加入新freq对应的链表中,若该链表不存在,则先创建该链表 if (preList->freq != node->freq) { FreqNode *newList = new FreqNode(node->freq); addFreqNode(newList, preList); newList->addDataNodeFirst(node); } else preList->addDataNodeFirst(node); } void removeFreqNode(FreqNode *node) { //频率结点双向链表中表头代表最高的使用频率 node->prior->after = node->after; //表尾代表最低的使用频率 node->after->prior = node->prior; } void addFreqNode(FreqNode *newList, FreqNode *preList) { //往频率结点双向链表插入结点 newList->after = preList->after; newList->after->prior = newList; newList->prior = preList; preList->after = newList; } public: LFUCache(int capacity) { _capacity = capacity; DHead = new FreqNode(); DTail = new FreqNode(); DHead->after = DTail; DTail->prior = DHead; } ~LFUCache() { delete DHead; delete DTail; } int get(int key) { if (cache.find(key) != cache.end()) { DataNode *node = cache[key]; freqInc(node); //增加使用频率、最近使用过 return node->val; } return -1; } void put(int key, int value) { if (_capacity == 0) return; if (cache.find(key) != cache.end()) { //已存在该key DataNode *node = cache[key]; node->val = value; //修改值 freqInc(node); //增加使用频率、最近使用过 } else { //不存在该key if (cache.size() == _capacity) { //容量已满 DataNode *temp = DTail->prior->tail->prev; //频率最低、最近最少使用的键值 cache.erase(temp->key); //移除这一映射 //如果缓存满了,则删除DTail->prior链表中的tail->prev的node DTail->prior->removeDataNode(temp); delete temp; //如果该链表已被删空,则删除该链表 if (DTail->prior->head->next == DTail->prior->tail) removeFreqNode(DTail->prior); } DataNode *newNode = new DataNode(key, value); cache[key] = newNode; //记录key:newNode之间的映射 if (DTail->prior->freq != 1) { //新数据结点要插入使用频率为1次的数据结点双向链表中 FreqNode *newList = new FreqNode(1); addFreqNode(newList, DTail->prior); //在DTail->prior之后插入新链表 newList->addDataNodeFirst(newNode); } else DTail->prior->addDataNodeFirst(newNode); //插入到DTail->prior中 } } };要注意的是，我们使用了二维双向链表，即双向链表的结点也是双向链表。通过使用双向链表（添加虚拟头结点和虚拟尾结点是为了统一操作），可以对任意已知结点进行 O ( 1 ) O(1) O(1) 删除——对于LRU来说，删除功能用于移除结点以更新最近使用的性质（然后添加到表头）、在容量已满时从表尾删除结点；对LFU来说，删除功能用于删除空的数据结点双向链表（容量已满时删除数据结点导致空表、移动结点到更高频率链表上导致空表）。可以看出，这两者都需要在任意位置进行删除。
还需要的是添加结点的功能。对于LRU而言，总是在表头添加结点，做到 O ( 1 ) O(1) O(1) 是很简单的；对于LFU而言，一方面需要在表尾添加代表新的最低频率的结点，另一方面由于增加结点使用次数，要求移动结点到更高频率链表（的表头，LRU实现的方法），需要创建并插入新的频率结点，于是需要在任意位置进行插入。这一点有所不同。
最后，通过键查找值的功能是由哈希映射实现的，它也承担着表达LFU缓存大小的功能。如果容量已满，就需要移除映射；否则直接插入新的键值对。
