LRU 缓存机制 题目描述 设计一个 LRU（最近最少使用）缓存机制，支持 get 和 put 操作。 缓存容量为 capacity ，若关键字已存在则更新值，否则插入；当缓存满时，删除最久未使用的关键字。 get(key) ：若关键字存在则返回值，否则返回 -1。 put(key, value) ：若关键字存在则更新值，否则插入；若超出容量则删除最久未使用的关键字。 要求所有操作的时间复杂度为 O(1) 。 解题思路 核心需求分析 快速查找键值对 → 使用 哈希表 （O(1) 查询）。 维护访问顺序 → 需要一种能快速移动元素到头部、删除尾部元素的数据结构 → 双向链表 （O(1) 增删）。 数据结构设计 哈希表： unordered_map<int, Node*> ，键映射到链表节点。 双向链表：节点包含 key, value, prev, next 。链表头部存放最近访问的节点，尾部存放最久未使用的节点。 操作细节 get(key) ： 若哈希表中不存在 key，返回 -1。 若存在，通过哈希表定位节点，将其移动到链表头部（先删除后插入头部），返回值。 put(key, value) ： 若 key 已存在：更新值，并移动节点到头部。 若 key 不存在： 创建新节点，插入链表头部并更新哈希表。 若缓存已满（当前大小 ≥ capacity），删除链表尾部节点，并删除哈希表中对应键。 步骤演示（示例：capacity=2） put(1, 10) ：链表 [ 1:10 ]，哈希表 {1→节点1}。 put(2, 20) ：链表 [ 2:20, 1:10 ]，哈希表 {1→节点1, 2→节点2}。 get(1) ：移动 1 到头部 → 链表 [ 1:10, 2:20 ]，返回 10。 put(3, 30) （满）：删除尾部节点 2:20 → 链表 [ 3:30, 1:10 ]，哈希表删除键 2，加入键 3。 get(2) ：键 2 不存在，返回 -1。 关键技巧 使用 伪头节点和伪尾节点 （dummy head/tail）简化链表边界操作。 将节点操作封装为独立方法（如 addToHead 、 removeNode 、 moveToHead ），避免重复代码。 复杂度分析 哈希表操作 O(1)，链表操作 O(1)，整体满足 O(1) 要求。 通过结合哈希表与双向链表，即可高效实现 LRU 缓存机制。