LRU缓存
“LRU 缓存”问题的详细指南和 Python 实现。
1. 学习
“LRU 缓存”问题是链表部分的一个关键挑战。
此实现侧重于 Python 中的简单级逻辑。
在我们提供的解决方案中，我们优先考虑技术准确性和代码可读性。
2. Real-World Applications
3. Visual Intuition
可视化 LRU 缓存的逻辑流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔细阅读 LRU 缓存的问题陈述。
2. Formulate brute force
起草一个简单的迭代解决方案。
3. Identify inefficiency
寻找冗余计算。
4. Optimize search path
使用散列或排序来加速该过程。
5. Final Implementation
清理生产标准代码。
问题陈述
设计一个遵循最近最少使用 (LRU) 缓存约束的数据结构。
实现LRUCache类：
- LRUCache(capacity: int) - 使用正大小的容量初始化 LRU 缓存。
- get(key: int) -> int - 如果键存在则返回键的值，否则返回-1。
- put(key: int, value: int) -> None - 如果键存在则更新键的值。否则，将键值对添加到缓存中。如果密钥数量超过容量，则逐出最近最少使用的密钥。
get 和 put 函数必须以 O(1) 平均时间复杂度运行。
输入是操作列表和参数列表。实现一个返回结果列表的函数 lruCache(operations: list, arguments: list) -> list （对于构造函数和 put 为 None）。
- •1 <= capacity <= 3000
- •0 <= key <= 10000
- •0 <= value <= 100000
- •At most 200000 calls will be made to get and put
示例
["LRUCache","put","put","get","put","get","put","get","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
[None,None,None,1,None,-1,None,-1,3,4]
Cache capacity is 2. put(1,1), put(2,2), get(1) returns 1. put(3,3) evicts key 2. get(2) returns -1 (evicted). put(4,4) evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.
Need a Hint?
Edge Cases to Watch
- 空输入结构
- 单元素输入
- 大数值范围
准备好解决了吗？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面试见解和变化
复杂性分析分解
为什么时间: Directly evaluates all possibilities.
为什么选择太空: Uses standard local memory.
为什么时间: Optimized paths reduce total operations.
为什么选择太空: May trade memory for speed.
优化解决方案Python代码
优化解决方案Python代码
class DNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCacheOpt:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.left = DNode(0, 0)
self.right = DNode(0, 0)
self.left.next = self.right
self.right.prev = self.left
def _remove(self, node):
prev, nxt = node.prev, node.next
prev.next = nxt
nxt.prev = prev
def _insert(self, node):
prev, nxt = self.right.prev, self.right
prev.next = node
nxt.prev = node
node.prev = prev
node.next = nxt
def get(self, key: int) -> int:
if key in self.cache:
self._remove(self.cache[key])
self._insert(self.cache[key])
return self.cache[key].val
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
self.cache[key] = DNode(key, value)
self._insert(self.cache[key])
if len(self.cache) > self.cap:
lru = self.left.next
self._remove(lru)
del self.cache[lru.key]暴力破解代码（剧透保护）
暴力破解代码（剧透保护）
class LRUCacheBrute:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.usage = []
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.usage.remove(key)
self.usage.append(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.usage.remove(key)
elif len(self.cache) >= self.cap:
lru = self.usage.pop(0)
del self.cache[lru]
self.cache[key] = value
self.usage.append(key)Algorithm Pattern Checklist
When dealing with Linked List data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推荐的 Python 资源
通过相关的交互式教程、备忘单和代码比较来扩展您的知识。
Python 循环：For 和 While 循环解释
了解如何使用 Python 循环来迭代数据。通过交互式示例掌握 for 循环、while 循环、break、continue 和循环最佳实践。
如何在 Python 中对列表进行排序（升序和降序）
了解如何在 Python 中使用 sort() 方法和sorted() 函数对列表进行排序。发现自定义键排序和逆序示例。
Python 字符串方法备忘单
Python 字符串操作的完整参考指南。掌握格式化、搜索、拆分、替换和检查字符串属性。
Python 与 JavaScript：哪种编程语言最好？
Python 和 JavaScript 的全面比较。探索语法差异、性能、用例（后端与前端）和编码示例。