解题思路
本题要求实现 LRU 缓存，核心算法是哈希表加双向链表。
哈希表用于根据 key 快速找到缓存中的数据，双向链表用于维护访问顺序：
- 最近使用的节点放在链表头部。
- 最久未使用的节点在链表尾部。
- 执行 get 时，如果 key 存在，就把它移动到最近使用位置。
P4899.LRU缓存
题目描述
请你设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构。
LRU 缓存需要支持两种操作：
- get key：如果关键字 key 存在于缓存中，则返回关键字对应的值；否则返回 −1。
- put key value：如果关键字 key 已经存在，则修改其对应的值为 value；如果不存在，则向缓存中插入该组 key−value。如果插入后缓存中的关键字数量超过容量 capacity，则需要删除最久未使用的关键字。
当一个关键字被 get 或 put 访问时，它会变成最近使用的关键字。
请处理 m 次操作，并输出所有 get 操作的结果。
要求 get 和 put 的平均时间复杂度均为 O(1)。
输入描述
第一行输入两个整数 capacity 和 m，分别表示 LRU 缓存的容量和操作次数。
接下来 m 行，每行表示一次操作，格式如下：
- get key
- put key value
其中：
- capacity 表示缓存容量。
- m 表示操作次数。
- key 表示关键字。
- value 表示关键字对应的值。
输出描述
对于每一次 get 操作，输出一行结果。
如果 key 存在于缓存中，则输出对应的 value；否则输出 −1。
样例 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
解释
put 1 1 后，缓存为 1=1。
put 2 2 后，缓存为 1=1, 2=2。
get 1 返回 1，关键字 1 变为最近使用。
put 3 3 时，关键字 2 最久未使用，因此删除 2，缓存为 1=1, 3=3。
get 2 返回 −1。
put 4 4 时，关键字 1 最久未使用，因此删除 1，缓存为 3=3, 4=4。
get 1 返回 −1。
get 3 返回 3。
get 4 返回 4。
样例 2
输入
1 6
put 1 10
get 1
put 2 20
get 1
get 2
put 2 30
输出
10
-1
20
解释
缓存容量 capacity=1。
put 1 10 后，缓存为 1=10。
get 1 返回 10。
put 2 20 时，缓存容量已满，关键字 1 被删除，缓存为 2=20。
get 1 返回 −1。
get 2 返回 20。
put 2 30 修改关键字 2 的值，缓存为 2=30。由于该操作不是 get 操作，因此不输出结果。
数据范围
- 1≤capacity≤3000
- 1≤m≤2×105
- 0≤key≤10000
- 0≤value≤105
