leetcode460.LFU缓存「2020-0405」
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
一个项目的使用次数就是该项目被插入后对其调用 get 和 put 函数的次数之和。使用次数会在对应项目被移除后置为 0。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题是让我们实现最近不常用页面置换算法LFU (Least Frequently Used), 之前我们做过一道类似的题LRU Cache，让我们求最近最少使用页面置换算法LRU (Least Recnetly Used)。两种算法虽然名字看起来很相似，但是其实是不同的。顾名思义，LRU算法是首先淘汰最长时间未被使用的页面，而LFU是先淘汰一定时间内被访问次数最少的页面。光说无凭，举个例子来看看，比如说我们的cache的大小为3，然后我们按顺序存入 5，4，5，4，5，7，这时候cache刚好被装满了，因为put进去之前存在的数不会占用额外地方。那么此时我们想再put进去一个8，如果使用LRU算法，应该将4删除，因为4最久未被使用，而如果使用LFU算法，则应该删除7，因为7被使用的次数最少，只使用了一次。相信这个简单的例子可以大概说明二者的区别。
参考：https://www.cnblogs.com/grandyang/p/6258459.html
参考：
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/lfu-cache/solution/lfuhuan-cun-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Node:
def __init__(self, key, val, pre=None, nex=None, freq=0):
self.pre = pre
self.nex = nex
self.freq = freq
self.val = val
self.key = key
def insert(self, nex):
nex.pre = self
nex.nex = self.nex
self.nex.pre = nex
self.nex = nex
def create_linked_list():
head = Node(0, 0)
tail = Node(0, 0)
head.nex = tail
tail.pre = head
return (head, tail)
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.size = 0
self.minFreq = 0
self.freqMap = collections.defaultdict(create_linked_list)
self.keyMap = {}
def delete(self, node):
if node.pre:
node.pre.nex = node.nex
node.nex.pre = node.pre
if node.pre is self.freqMap[node.freq][0] and node.nex is self.freqMap[node.freq][-1]:
self.freqMap.pop(node.freq)
return node.key
def increase(self, node):
node.freq += 1
self.delete(node)
print(self.freqMap[node.freq][-1].pre.val)
self.freqMap[node.freq][-1].pre.insert(node)
if node.freq == 1:
self.minFreq = 1
elif self.minFreq == node.freq - 1:
head, tail = self.freqMap[node.freq - 1]
if head.nex is tail:
self.minFreq = node.freq
def get(self, key: int) -> int:
if key in self.keyMap:
self.increase(self.keyMap[key])
return self.keyMap[key].val
return -1
def put(self, key: int, value: int) -> None:
if self.capacity != 0:
if key in self.keyMap:
node = self.keyMap[key]
node.val = value
else:
node = Node(key, value)
self.keyMap[key] = node
self.size += 1
if self.size > self.capacity:
self.size -= 1
deleted = self.delete(self.freqMap[self.minFreq][0].nex)
self.keyMap.pop(deleted)
self.increase(node)
作者：ccluqh
