题目描述
实现一个 LRU（最近最少使用）缓存机制。支持 get 和 put 两个操作：get(key) 获取数据，put(key, value) 写入数据。当缓存达到容量上限时，淘汰最近最少使用的数据。
示例
输入：capacity = 2; put(1,1); put(2,2); get(1); put(3,3); get(2)
输出：get(1) 返回 1; get(2) 返回 -1（已被淘汰）
提示
Python 3.7+ 的 dict 保持插入顺序，可以利用这个特性。每次访问时先删除再插入，使该 key 成为最新。或者使用 collections.OrderedDict 的 move_to_end() 方法。
参考答案
from collections import OrderedDict
class LRUCache:
"""LRU 缓存实现"""
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
"""获取缓存数据"""
if key not in self.cache:
return -1
# 移到末尾表示最近使用
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
"""写入缓存数据"""
if key in self.cache:
# 已存在则更新值并移到末尾
self.cache.move_to_end(key)
self.cache[key] = value
# 超出容量则淘汰最久未使用的（第一个元素）
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
# 测试
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # 淘汰 key=2
print(cache.get(2)) # -1（已被淘汰）
cache.put(4, 4) # 淘汰 key=1
print(cache.get(1)) # -1（已被淘汰）
print(cache.get(3)) # 3
print(cache.get(4)) # 4