理论基础
LRU 算法、Cache
实现 LRU Cache 缓存机制
题目描述
设计和实现一个 LRU Cache 缓存机制
解题思路
- least recently used 最近最少使用 (被淘汰)
- Double LinkedList (双向链表)
- O (1) 查询头部
- O (1) 修改、更新
- 实现读、写缓存的操作
Python 解法
class LRUCache(object): def __init__(self, capacity): self.dic = collection.OrderedDict() self.remain = capacity def get(self, key): if key not in self.dic: return -1 v = self.dic.pop(key) self.dic[key] = v # 把当前访问的key设置为最新 return v def put(self, key, value): if key in self.dic: self.dic.pop(key) else: if self.remain > 0: self.remain -= 1 else: # 如果容量已满 self.dic.popitem(last=False) # 删除最后一个键值对 self.dic[key] = value
© 著作权归作者所有
举报
发表评论
0/200