核心内容摘要
91好莱坞：复古浪潮中的璀璨明珠，重燃旧日经典魅力
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现LRUCache类LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中则返回关键字的值否则返回-1。
void put(int key, int value)如果关键字key已经存在则变更其数据值value如果不存在则向缓存中插入该组key-value。
如果插入操作导致关键字数量超过capacity则应该逐出最久未使用的关键字。
函数get和put必须以O(
的平均时间复杂度运行。
示例输入[LRUCache, put, put, get, put, get, put, get, get, get] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出[null, null, null, 1, null, -1, null, -1, 3, 4]解释LRUCache lRUCache new LRUCache(
; lRUCache.put(1,
; // 缓存是 {11} lRUCache.put(2,
; // 缓存是 {11, 22} lRUCache.get(
; // 返回 1 lRUCache.put(3,
; // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(
; // 返回 -1 (未找到) lRUCache.put(4,
; // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(
; // 返回 -1 (未找到) lRUCache.get(
; // 返回 3 lRUCache.get(
; // 返回 4提示1 capacity 30000 key 100000 value 最多调用2 * 105次get和put解题思路数据结构选择OrderedDict既保留了哈希表的 O (
查找特性又维护了元素的插入顺序通过move_to_end和popitem可以在 O (
时间内完成「标记最近使用」和「淘汰最久未使用」的操作。
get操作若 key 不存在直接返回-1。
若 key 存在将其移动到字典末尾标记为「最近使用」再返回对应值。
put操作若 key 已存在更新值并移动到末尾标记为「最近使用」。
若 key 不存在直接添加到末尾。
若添加后超出容量删除字典头部的元素最久未使用的键。
复杂度分析时间复杂度get和put操作均为O(
因为OrderedDict的move_to_end、popitem和哈希表的增删改查都是 O (
时间。
空间复杂度O(capacity)最多存储capacity个键值对。
Python代码from collections import OrderedDict class LRUCache: def __init__(self, capacity: int): self.cache OrderedDict() self.capacity capacity def get(self, key: int) - int: if key not in self.cache: return -1 # 将访问的键移到末尾表示最近使用 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) - None: if key in self.cache: # 键已存在更新值并移到末尾 self.cache.move_to_end(key) self.cache[key] value # 检查容量超出则删除最久未使用的键头部元素 if len(self.cache) self.capacity: self.cache.popitem(lastFalse) # ------------------------------ 测试驱动代码 ------------------------------ def run_operations(ops, params): 执行操作序列返回每个操作的结果 :param ops: 操作类型列表如[LRUCache, put, get] :param params: 对应每个操作的参数列表 :return: 操作结果列表与题目输出格式一致 obj None result [] for op, param in zip(ops, params): if op LRUCache: obj LRUCache(*param) result.append(None) elif op get: res obj.get(*param) result.append(res) elif op put: obj.put(*param) result.append(None) return result # 题目示例输入 if __name__ __main__: ops [LRUCache,put,put,get,put,get,put,get,get,get] params [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]] # 执行并打印结果 output run_operations(ops, params) print(输出结果:, output) # 验证是否与题目输出一致 expected [None, None, None, 1, None, -1, None, -1, 3, 4] print(是否符合预期:, output expected)LeetCode提交代码class LRUCache: def __init__(self, capacity: int): self.cache OrderedDict() self.capacity capacity def get(self, key: int) - int: if key not in self.cache: return -1 # 将访问的键移到末尾表示最近使用 self.cache.move_to_end(key) return self.cache[key] def put(self, key: int, value: int) - None: if key in self.cache: # 键已存在更新值并移到末尾 self.cache.move_to_end(key) self.cache[key] value # 检查容量超出则删除最久未使用的键头部元素 if len(self.cache) self.capacity: self.cache.popitem(lastFalse) # Your LRUCache object will be instantiated and called as such: # obj LRUCache(capacity) # param_1 obj.get(key) # obj.put(key,value)程序运行截图展示
总结本文介绍了LRU缓存机制的实现方法。
通过使用Python的OrderedDict数据结构既保证了O(
时间复杂度的查找操作又维护了元素的访问顺序。
当缓存容量超出时自动淘汰最久未使用的元素。
该实现满足题目要求的get和put操作均为O(
时间复杂度并通过测试用例验证了正确性。
关键点在于利用OrderedDict的move_to_end和popitem方法高效处理最近访问标记和元素淘汰。