LeetCode.jpg
146. LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
Python3 实现
LRU(最近最少使用) 缓存机制
更多可参见：
https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_recently_used_(LRU)
# @author:leacoder
# @des: LRU(最近最少使用) 缓存机制
# OrderedDict 参看 https://docs.python.org/3/library/collections.html#collections.OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.dic = collections.OrderedDict() # OrderedDict 记住了字典元素的添加顺序
self.remain = capacity # 容量 大小
def get(self, key: int) -> int:
if key not in self.dic:
return -1
v = self.dic.pop(key)
self.dic[key] = v # 被获取 刷新最近使用
return v
def put(self, key: int, value: int) -> None:
if key in self.dic:
self.dic.pop(key) # 如果字典中有先弹出 再加入
else: # 没有
if self.remain > 0: # 字典未满
self.remain -= 1 # 剩余容量 -1
else: # 字典已满 弹出最近最少使用的，最老的元素
self.dic.popitem(last = False)
'''
popitem(last=True)
The popitem() method for ordered dictionaries returns and removes a (key, value) pair.
The pairs are returned in LIFO order if last is true or FIFO order if false.
'''
self.dic[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
GitHub链接：
https://github.com/lichangke/LeetCode
知乎个人首页：
https://www.zhihu.com/people/lichangke/
简书个人首页：
https://www.jianshu.com/u/3e95c7555dc7
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
