LFU(最常用)是一个著名的缓存回收算法。为一个缓存容量k,如果缓存已满,需要驱逐一个关键,租赁常用的关键将踢出。实现LFU缓存的设置和获取方法。
LFU是一个著名的缓存算法。实现LFU中的设置和获取
http://www.lintcode.com/en/problem/lfu-cache/
这道题让我们实现一个LRU缓存器,LRU是最近最少使用的简写,就是最近最少使用的意思,那么这个缓存器主要有两个成员函数,获取和设置,其中得到函数是通过输入关键来获得价值,如果成功获得后,这对(键值)升至缓存器中最常用的位置(顶部),如果关键不存在,则返回1。而设置函数是插入一对新的(键,值),如果原缓存器中有该键,则需要先删除掉原有的,将新的插入到缓存器的顶部。如果不存在,则直接插入到顶部。若加入新的值后缓存器超过了容量,则需要删掉一个最不常用的值,也就是底部的值。具体实现时我们需要三个私有变量,帽,l和m,其中帽是缓存器的容量大小,l是保存缓存器内容的列表,m是哈希表,保存关键值的关键和缓存器各项的迭代器之间映射,方便我们以O(1)的时间内找到目标项。
http://www.jiuzhang.com/solutions/lfu-cache/
