LRU 缓存

LRU Cache

问题：LRU 缓存

考察：哈希表、链表、设计

来源：DSA Prep / Citadel

链接：https://www.dsaprep.dev/blog/lru-cache-leetcode-solution

Problem: LRU Cache

Patterns: Hash Table, Linked List, Design

Recency: 2yr

Link: https://www.dsaprep.dev/blog/lru-cache-leetcode-solution

Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/

解析

思路：用哈希表定位节点，用双向链表维护最近使用顺序。访问或更新节点时移动到链表头，容量超限时删除链表尾部节点。

复杂度：get/put 平均 O(1)，空间 O(capacity)。