请你设计并实现一个满足 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) 的平均时间复杂度运行。
示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -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
提示:
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
下面是本人的一些废话，不感兴趣可直接看实现过程
看完题目，看到函数 get 和 put 必须以 O(1) 的平均时间复杂度运行，第一反应是顺序存储的随机存取才可以实现O(1)的时间复杂度，也就是说一定会有一块连续的存储空间存储数据，且大小为capacity。可以把key对应连续的存储空间的下标，但是看到提示里面的key的范围超出了capacity的范围，那如何在让key在[0,capacity]循环呢？脑子直接想到了循环队列的取余法，因为最近用循环队列比较频繁。
但是，经过取余后，还是会造成出现重复的key，该怎们解决呢？突然想到数据结构里面的散列表的碰撞的处理，立马去看关于散列表的介绍，以前没学的东西，现在又冒出来找我了。
看了以后，觉得很神奇，原来取余法是散列函数的一种，并使用频繁的一种。然后又看了关于碰撞的处理，书上介绍两种，第一种叫开地址法，第二种方法叫拉链法。
解决了碰撞问题，那么如何实现最近最少使用，一想到这是关于链表的题目，慢慢想到了循环单链表，头插法实现最近使用，而尾结点一定是最少使用，也就是当缓存空间达到capacity时，需要删除的。但是写了一半代码，发现当访问结点为尾结点时，需要更改尾结点，也就是需要尾结点的前驱。我知道，在单链表中，寻找某个结点前驱时间复杂度是O(n)，不符合题意，立马把代码删除。
经过思考，心情里变得比较烦躁，但又不想看题解，因为想着现在正是考验我的时候，想着这道题一定想要教会我什么。尝试让自己变得冷静，不断地翻开数据结构这本书，看到双向链表，哎，这不就是为了解决以O(1)时间复杂度访问某个结点前驱的问题嘛！为什么没有马上想到，是因为平时做的题目都是单链表，双向链表用的太少了…
以上问题都解决了后，刚开始使用开地址法的线性探查法解决碰撞时，发现最后几个测试用例超时了，但是，说明思路是对的，因为线性探访的最坏情况的时间复杂度就是O(n)。
然后改为使用了拉链法，写代码用的时间不多，调试用了很多时间，最终，在不放弃的情况下，终于找到了代码的某处错误。真是太不容易了，因为常规测试用例通过了，在一些复杂的测试用例没通过，又无法一步一步的调试，只能不断地阅读代码，最后发现是在某个很隐秘且常规测试用例很难覆盖的地方，我当场麻了…
所幸，最后还是一步一步的写出来了，还是非常开心的，感觉时间花的太值了！