LRU 缓存 (LRU Cache)¶

Deadline

2026年4月24日23:59

题目背景¶

LRU（Least Recently Used，最近最少使用）是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。其核心价值在于利用“时间局部性”原理，在内存空间有限的情况下优先保留近期活跃的数据，从而有效减少对低速磁盘或网络的访问，大幅提升系统的响应速度。

题目描述¶

请你使用 带头节点的双向链表，实现一个满足 LRU 缓存约束的数据结构。

要求双向链表内部节点按上一次被访问的时刻排序：

最近访问：缓存中上一次被访问时刻最近的节点，应作为头节点的后继（即链表的第一个有效节点）。
最久访问：缓存中上一次被访问时刻最远的节点，应处于双向链表的末尾。

该数据结构需要实现以下功能：

LRUCache(int capacity)：以非负整数作为容量 capacity 初始化 LRU 缓存，返回一个指向双向链表头节点的指针。
int get(int key)：如果关键字 key 存在于缓存中，则返回关键字 key 对应的值 value，并将该节点移动到链表头部（头节点之后）；否则返回 -1。
void put(int key, int value)：
如果关键字 key 已经存在，则变更其对应的值为新的 value，并将其移动到链表头部。
如果关键字 key 不存在，则将这组 key-value 插入缓存（链表头部）。
若此次插入导致缓存数量超过 capacity，则应删去缓存中最久未使用的 key-value（即链表末尾节点）。

为了方便你理解 LRU 缓存的运行机制，这里提供一个 容量为 2 的最简样例及详细的操作步骤说明。

最简样例 (Minimal Example)¶

输入
2 5
put 1 10
put 2 20
get 1
put 3 30
get 2
输出
10 -1 
样例说明 (Sample Walkthrough)¶

假设双向链表的结构为：Head <-> Node1 <-> Node2 <-> ... <-> Tail （其中 Head 为不存储数据的头节点，Node1 为最近访问，末尾节点为最久访问）

初始化：

容量 capacity = 2。

链表状态：Head <-> Tail (空)

put 1 10：

关键字 1 不存在，直接插入到头节点后。

链表状态：Head <-> [1:10] <-> Tail

缓存内容：{1: 10}

put 2 20：

关键字 2 不存在，插入到头节点后。

链表状态：Head <-> [2:20] <-> [1:10] <-> Tail

缓存内容：{1: 10, 2: 20}

说明：[2:20] 是最新访问的，所以排在最前面。

get 1：

关键字 1 存在，返回其值 10。

关键动作：根据 LRU 规则，1 被访问了，需要移动到头节点后。

链表状态：Head <-> [1:10] <-> [2:20] <-> Tail

输出：10

put 3 30：

关键字 3 不存在。此时缓存长度为 2，已达到容量上限。

淘汰操作：删去链表末尾最久未使用的节点（即 [2:20]）。

插入操作：将 [3:30] 插入到头节点后。

链表状态：Head <-> [3:30] <-> [1:10] <-> Tail

缓存内容：{1: 10, 3: 30}

get 2：

关键字 2 已在步骤 5 中被淘汰。

输出：-1

输入格式¶

输入共包含两部分：

第一行输入两个非负整数：capacity（容量）和 n（操作总次数）。
接下来的 n 行，每行代表一个操作，格式为 put key value 或 get key。

输出格式¶

输出一行，包含所有 get 操作的结果，以空格分隔。如果某个 get 操作未命中，输出 -1。

数据范围¶

capacity、key、value 均为非负 int 型。
操作次数 n 视具体测试样例而定。

时间限制¶

1 秒

内存限制¶

128 MB

样例 1¶

输入¶

2 9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

输出¶

1 -1 -1 3 4

样例 2¶

输入¶

0 0

输出¶

(无输出)

样例 3¶

输入¶

3 16
put 1 1
put 2 2
get 3
put 3 3
get 2
put 3 33
get 1
put 4 4
get 2
get 3
put 5 5
get 1
get 2
get 3
get 4
get 5

输出¶

-1 2 1 -1 33 -1 -1 33 4 5

提示¶

思考题：如何设计函数 get() 和 put() 使其以 O(1) 的平均时间复杂度运行？
提示：尝试结合哈希表（Hash Map）与双向链表。
链表操作：在 put 和 get 时，涉及到节点的“提前”操作，即从当前位置删除并插入到头节点之后。

实现要求¶

核心结构：必须使用带头节点的双向链表实现。
指针操作：必须显式地进行指针管理，严禁仅使用数组下标模拟。
多文件开发：建议将项目拆分为 main.c（处理输入输出）、lru.c（核心逻辑）和 lru.h（结构定义与函数声明）。
构建工具：工程需支持通过 Makefile 或 CMakeLists.txt 进行构建。
注意：平台无法进行CMake编译，所以需要同学将所有文件放在同一目录下。