填空题

LRU Cache

Question

	设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。

int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。
void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。

请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。

限制：请在O(1)的时间复杂度内完成上述2个操作。

输入描述： 第一行读入一个整数n，表示LRU Cache的容量限制。 从第二行开始一直到文件末尾，每1行代表1个操作。

如果每行的第1个字符是p，则该字符后面会跟随2个整数，表示put操作的key和value。

如果每行的第1个字符是g，则该字符后面会跟随1个整数，表示get操作的key。输入样例： 2 p 1 1 p 2 2 g 1 p 2 102 p 3 3 g 1 g 2 g 3 输出描述： 按照输入中get操作出现的顺序，按行输出get操作的返回结果。输出样例 1 1 -1 3