解题思路

本题要求实现 $LRU$ 缓存，核心算法是哈希表加双向链表。

哈希表用于根据 $key$ 快速找到缓存中的数据，双向链表用于维护访问顺序：

• 最近使用的节点放在链表头部。
• 最久未使用的节点在链表尾部。
• 执行 $get$ 时，如果 $key$ 存在，就把它移动到最近使用位置。

题目描述

请你设计并实现一个满足 $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 \le capacity \le 3000$
• $1 \le m \le 2 \times 10^5$
• $0 \le key \le 10000$
• $0 \le value \le 10^5$