LeetCode热题100-LRU 缓存

LRU Least Recently Used最近最少使用题目要求所有操作必须O(1)所以只能使用哈希 双向链表实现。使用现成OrderedDictfrom collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.cache OrderedDict() def get(self, key: int) - int: if not key in self.cache: return -1 self.cache.move_to_end(key, lastFalse) # 将书放到链首 return self.cache[key] def put(self, key: int, value: int) - None: self.cache[key] value self.cache.move_to_end(key, lastFalse) if len(self.cache) self.capacity: self.cache.popitem() # 去掉最后一本书自己实现(后续补充)