LRU 缓存机制 题目描述 设计一个 LRU（最近最少使用）缓存机制，需要实现以下功能： LRUCache(int capacity) 以正整数 capacity 作为容量初始化缓存。 int get(int key) 如果关键字 key 存在于缓存中，则返回其对应的值，并将该关键字提升为“最近使用”；否则返回 -1 。 void put(int key, int value) 如果 key 已存在，则更新其值并提升为最近使用；如果不存在，则插入该键值对。若插入后缓存容量超过 capacity ，则删除最久未使用的键值对。 要求所有操作的时间复杂度为 O(1) 。 解题思路 核心需求分析 快速查找 ：通过 key 获取 value ，需使用哈希表（如 unordered_map ）实现 O(1) 查询。 维护访问顺序 ：需高效维护键的“使用顺序”，支持快速删除最久未使用的键，并将最近使用的键移动到前端。 数据结构选择 哈希表 ：存储 key 到对应节点的迭代器（或指针），实现 O(1) 查找。 双向链表 ：每个节点存储 (key, value) 。链表头部表示最近使用，尾部表示最久未使用。支持 O(1) 时间删除节点（通过指针）和插入头部。 操作逻辑 Get 操作 ： 若 key 不存在，返回 -1 。 若存在，通过哈希表定位链表节点，将其移动到链表头部，并返回 value 。 Put 操作 ： 若 key 存在，更新值并移动节点到头部。 若不存在： 创建新节点，插入链表头部。 将 key 和节点指针存入哈希表。 若容量超限，删除链表尾部节点，并删除哈希表中对应键。 详细步骤示例 假设 capacity = 2 ，操作序列如下： 初始化 ：缓存为空，哈希表 map 和双向链表 list 均为空。 put(1, 10) ： 创建节点 (1, 10) ，插入链表头部： list = [1:10] 。 更新哈希表： map = {1 -> 节点指针} 。 put(2, 20) ： 创建节点 (2, 20) ，插入头部： list = [2:20, 1:10] 。 更新哈希表： map = {1 -> 节点1, 2 -> 节点2} 。 get(1) ： key=1 存在，返回值 10。 将节点1移动到头部： list = [1:10, 2:20] 。 put(3, 30) （容量已满，需淘汰）： 创建节点 (3, 30) ，插入头部： list = [3:30, 1:10] 。 删除尾部节点 2:20 ，更新哈希表：移除 key=2，加入 key=3。 关键实现技巧 使用 双向链表 而非单向链表，以便在 O(1) 时间内删除中间节点（需知道前驱节点）。 哈希表存储 key 到 链表迭代器 （C++）或指针（Python 自定义节点），避免重复查找链表。 将“移动节点到头部”拆解为： 删除原有节点。 在头部插入新节点。 复杂度分析 时间复杂度： get 和 put 均为 O(1)。 空间复杂度：O(capacity)，用于存储哈希表和链表。 通过结合哈希表与双向链表，即可高效实现 LRU 缓存机制。