LRU 缓存：ACM 模式刷题
按标准输入读取测试数据，输出结果后可在 CodeACM 在线运行和提交。
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
· LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
· int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
· void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
输入格式
第一行输入缓存容量 capacity 和操作数 q。
接下来 q 行为操作：get key，或 put key value。
输出格式
每个 get 操作输出一行：若键存在则输出对应值，否则输出 −1。put 操作不输出。
数据范围
- 1 ≤ capacity ≤ 3000
- 1 ≤ q ≤ 2 × 10⁵
- 0 ≤ key, value ≤ 10⁴
公开样例
样例 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
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1（未找到）
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1（未找到）
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
样例 2
输入
1 4 put 2 1 get 2 put 3 2 get 2
输出
1 -1
容量为 1，写入键 3 时淘汰键 2。
练习建议
先根据输入输出格式写出可运行程序，再用公开样例检查结果；遇到边界情况时，补充自测用例后提交。