题目内容

本题目要求你设计并实现一个采用最近最少使用（LRU）淘汰策略的缓存组件。该组件需要维护若干键值对，并在缓存达到容量上限后，优先移除最长时间没有被访问过的键值对。

请实现一个名为 LRUCache 的类，它包含以下能力：

• 构造函数 LRUCache(int capacity)：使用给定的整数 capacity 初始化缓存容量。
• 方法 get(int key)：根据 key 查询缓存。如果 key 存在，则返回它对应的值；否则返回 -1。
• 方法 put(int key, int value)：向缓存写入一个键值对。如果 key 已经存在，则更新它的值为 value；如果 key 不存在，则将其插入缓存。若插入后缓存中的键值对数量超过容量上限，则需要淘汰当前最久未被访问的键。

get 与 put 操作的平均时间复杂度必须为 $O(1)$。

约束条件

• 缓存容量 capacity 的取值范围为 1 到 3000。
• 键 key 的取值范围为 0 到 10000。
• 值 value 的取值范围为 0 到 10^5。
• get 与 put 的操作总次数最多为 2 * 10^5。

输入描述

所有操作均以 LRUCache 类的方法调用形式传入参数：

• 构造函数 LRUCache(int capacity)：传入一个整数 capacity，表示缓存的最大容量。
• 方法 get(int key)：传入一个整数 key，表示需要查询的关键字。
• 方法 put(int key, int value)：传入两个整数 key 和 value，表示需要插入或更新的键值对。

输出描述

• get 方法返回一个整数：如果 key 存在于缓存中，则返回对应的值；否则返回 -1。
• put 方法没有返回值。

样例1

输入

2
put 10 100
put 20 200
get 10
put 20 201
put 30 300
get 10
get 20
get 30

输出

100
-1
201
300

说明

缓存容量为 2。

先插入键 10，值为 100；再插入键 20，值为 200。此时缓存中有键 10 和键 20。

get(10) 返回 100，并将键 10 移动到最近使用端，因此键 20 变为最久未使用。

put(20, 201) 更新键 20 的值为 201，并将键 20 移动到最近使用端，此时键 10 变为最久未使用。

put(30, 300) 插入新键，缓存已满，所以淘汰最久未使用的键 10。缓存中剩下键 20 和键 30。

因此 get(10) 返回 -1，get(20) 返回 201，get(30) 返回 300。

样例2

输入

1
put 5 100
get 5
put 6 101
get 5
get 6
put 6 102
get 6

输出

100
-1
101
102

说明

缓存容量为 1，最多只能保留一个键值对。

put(5, 100) 后缓存中只有键 5，值为 100。

get(5) 返回 100。

put(6, 101) 插入新键，因为容量只有 1，所以淘汰键 5。缓存变为只有键 6，值为 101。

get(5) 返回 -1，因为键 5 已经被淘汰。

get(6) 返回 101。

put(6, 102) 更新键 6 的值为 102，缓存中仍只有键 6。

get(6) 返回 102。

样例3

输入

3
put 4 40
put 5 50
put 6 60
get 4
put 7 70
get 5
get 6
get 4
get 7

输出

40
-1
60
40
70

说明

缓存容量为 3。

初始插入键 4、5、6，值分别为 40、50、60。最近使用顺序为 6、5、4，最久未使用的是键 4。

get(4) 返回 40，并将键 4 移到最近使用端，顺序变为 4、6、5，最久未使用的是键 5。

put(7, 70) 插入新键，缓存已满，因此淘汰最久未使用的键 5。缓存中剩下键 4、6、7，顺序为 7、4、6。

get(5) 返回 -1，因为键 5 已经被淘汰。

get(6) 返回 60，并将键 6 移到最近使用端，顺序变为 6、7、4。

get(4) 返回 40，并将键 4 移到最近使用端，顺序变为 4、6、7。

get(7) 返回 70。