请你实现 LRU 缓存机制（LC146），要求 get 和 put 操作的平均时间复杂度为 O(1)。
考察说明
考察数据结构组合、缓存淘汰策略与工程实现能力
回答思路
- 能说明 LRU 缓存的基本思想：最近最少使用的条目在缓存满时被淘汰
- 能组合哈希表与双向链表实现 O(1) 的 get 和 put
- 能正确处理缓存容量限制、更新已有 key 和淘汰最久未使用的条目
- 能解释为什么双向链表和哈希表配合能达到 O(1)
- 能处理边界情况，如容量为 0 或重复访问
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。