python-leetcode面试题解之第146题LRU缓存-题解.zip

LRU（Least Recently Used）缓存淘汰策略是计算机科学中常用的一种内存管理策略，它将最近最少使用的数据优先淘汰。在Python中，实现LRU缓存机制可以借助于`collections`模块中的`OrderedDict`或者`deque`双端队列。本题解将深入探讨第146题的LRU缓存问题，以及如何使用Python来解决此类问题。 我们来看题目的具体要求。LeetCode第146题名为"LRU缓存"，其核心任务是设计一个数据结构，该数据结构支持以下操作： 1. `put(key, value)`：如果`key`不存在，则插入键值对；如果`key`已经存在，则更新其对应的`value`。 2. `get(key)`：如果`key`存在，则返回其对应的`value`；如果`key`不存在，则返回`-1`。 为了实现LRU缓存，我们需要考虑两个关键点：存储键值对的容器以及如何根据LRU策略淘汰元素。这里我们选择使用`OrderedDict`，因为它会自动维护元素的插入顺序，即访问顺序。当缓存满时，新插入的元素会替换掉最早插入且未被访问过的元素。 下面是一个基于`OrderedDict`的LRU缓存实现： ```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 in self.cache: self.cache.move_to_end(key) return self.cache[key] else: return -1 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(last=False) # 移除最旧的元素，即LRU策略 ``` 在这个实现中，`OrderedDict`的`move_to_end()`方法用于将访问过的`key`移动到容器的末尾，表示最近被访问。`popitem(last=False)`则会删除最不常访问的元素，即最早插入的元素。 除了`OrderedDict`，还可以使用`deque`双端队列来实现LRU缓存。`deque`提供了高效的添加和移除元素的操作，适用于实现LRU策略。但这里我们主要讲解`OrderedDict`的实现方式。 在面试中，除了代码实现，我们还需要讨论LRU缓存的性能分析。`get`和`put`操作的时间复杂度都是O(1)，因为它们都是对`OrderedDict`的操作，而`OrderedDict`内部的键查找和更新都是常数时间。空间复杂度也是O(capacity)，因为我们需要存储最多`capacity`个键值对。 通过以上分析，我们可以看出，Python的`OrderedDict`为解决LRU缓存问题提供了一个简洁且高效的解决方案。在面试中，理解这种数据结构的特性和应用，以及如何利用它们解决问题，是展示编程技巧和算法理解能力的重要环节。