[LeetCode]LFU Cache

是一道很麻烦的题。我们可以参考LRU Cache的思路，存一个map用来记录key和对应的NodeList的关系，NodeList存的就是所有access频率相同的key/value pair按照LRU的顺序排序的序列。NodeList的实现就是简化版本的LRU Cache，我们不用考虑超出capacity的情况，我们只需要implement insert, delete, get, deleteLast，不需要特地考虑在LRU Cache中提升优先级的方法，因为access一次之后，其频率就会+1，那么我们就应该从当前NodeList中remove key/value pair，然后插入对于的频率+1的NodeList当中。插入的时候永远从头部插入，我们就可以保证NodeList的元素是按照LRU排序。deleteLast是为了当LFU超出容量时，remove频率最少的NodeList中least recently used的元素。对于NodeList，其也是一个hashmap + doubly linked list的结构，每一个node就是对应的NodeList，不同的NodeList对应不同的频率，从大到小排序。hashmap存的是key和对应的NodeList，同时还有head和tail指针记录首尾。对于get和put：

• get的话，我们找到对应的NodeList查询value，之后从当前NodeList中删除，插入当前NodeList频率+1的NodeList当中，没有的话需要自己新建
• put的话
• 如果LFU Cache中已经存在，过程和get类似
• 如果不存在，如果cache已经满了，删掉频率最低的NodeList中的最后一个元素，更新map。插入新元素到频率为1的NodeList当中，没有的话自己新建

操作都是常数时间。代码入选：

我们也可以用c++自带的list来implement，可以减少代码的行数。这样我们不需要自己实现NodeList，运用list的emplace方法可以实现常数时间对任意位置的插入。代码如下：