难度：困难
题目内容：
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
进阶：
你是否可以在 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
题解：
emmm看着蛮简单的就是有点麻烦
实际上有很多边界条件要考虑。。。
所以对着报错修改了好多好多遍
class LFUCache:
def __init__(self, capacity: int):
self.cache = {} # 每个元素是个长度为2的列表，分别是键值和使用次数
self.capacity = capacity
self.keylist = [] #按使用次数顺序排一个key的列表,emmm就倒序吧
def get(self, key: int) -> int:
if key in self.cache.keys():
for i in range(len(self.keylist)):
if self.keylist[i][0] == key:
self.keylist[i][1] += 1
if i > 0:
if self.keylist[i][1] >= self.keylist [i-1][1]:
self.keylist[i],self.keylist[i-1] = self.keylist[i-1],self.keylist[i]
break
return self.cache[key]
else:
return -1
def put(self, key, value):
if self.capacity == 0:
return
if key in self.cache.keys():
for i in range(len(self.keylist)):
if self.keylist[i][0] == key:
self.keylist.pop(i)
break
self.cache[key] = value
if len(self.cache) > self.capacity and len(self.keylist)>=1:
self.cache.pop(self.keylist[-1][0])
self.keylist.pop()
self.keylist.append([key,0])
if len(self.keylist)>1:
if self.keylist[-2][1] == 0:
self.keylist[-1],self.keylist[-2] = self.keylist[-2],self.keylist[-1]
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
