題目：
請你設計并實現一個滿足 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) 的平均時間復雜度運行。

解題思路：
閱讀了靈神的題解之后，總結一下自己的理解。
想象有一堆書很妙。
對于get：想閱讀一本書，那么我就需要從這堆書里面把書取出來，讀完之后再放到最上面。這里就涉及到三個步驟：
1、先從這一堆書中找到這本書
2、從這堆書里拿出這本書
3、再將這本書放回到這堆書最上面

對于put：想添加一本書，首先需要判斷有沒有這本書，如果有，就把他拿出來，更新value，再放回這堆書最上面。如果沒有，就先判斷這堆書容量是否以達到最大容量，如果達到了，就丟棄最下面那本書，因為最下面那本書代表最久每閱讀的書了，然后再將這本新書放到書堆上面。這里也涉及三個步驟：
1、首先獲取這本書，如果有就更新value。注意在獲取這本書的過程也要包含找書、拿書、再放書，所以可以封裝成一個方法。
2、如果沒有這本書，則判斷容量是否達到閾值。如果達到，則刪除最下面一本書。
3、將這本新書放到書堆最上面。

那么現在的問題就是，該用什么數據結構來表示這堆書呢？
題目中的要求是get和put的時間復雜度都要是O(1)，可以想到用鏈表來實現，因為如果我們知道這本書在鏈表中的位置，我們可以在O(1)的時間復雜度刪除它再將它添加到鏈表頭部。
那為什么要使用雙向鏈表呢？
因為我們有一個刪除最下面那本書的過程，也就是刪除鏈表尾節點，如果我們用單向鏈表的話，我們需要先遍歷鏈表找到尾節點，就會導致時間復雜度不滿足要求。
而添加一個哨兵節點是為了不用特殊處理鏈表為空的情況

那為什么還需要有一個哈希表呢
注意我在上面說的“如果我們知道這本書在鏈表中的位置，我們可以在O(1)的時間復雜度刪除它再將它添加到鏈表頭部”。
我們一開始肯定是不知道這本書在鏈表中的具體位置的，我們就需要先遍歷鏈表找到這本書，這樣的話時間復雜度也是不符合要求的。
所以，我們需要用key能夠在O(1)的時間復雜度內，找到這本書的位置，那么就可以用哈希表來存儲key到鏈表節點的映射關系。

代碼：

class LRUCache {private static class Node{int key;int value;Node pre;Node next;public Node(int key, int value){this.key = key;this.value = value;}  }private final int capacity;private final Node dummy = new Node(0, 0);private final Map<Integer, Node> keyToNode = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;dummy.next = dummy;dummy.pre = dummy;}public int get(int key) {Node node = getNode(key);return node == null ? -1 : node.value;}public void put(int key, int value) {Node node = getNode(key);if(node != null){node.value = value;return;}// 如果關鍵容量達到capacity，則刪除最久未使用的if(keyToNode.size() == capacity){Node lastNode = dummy.pre;keyToNode.remove(lastNode.key);remove(lastNode);}node = new Node(key, value);keyToNode.put(key, node);putFirst(node);}private Node getNode(int key){if(!keyToNode.containsKey(key)){return null;}Node node = keyToNode.get(key);remove(node);putFirst(node);return node;}private void remove(Node node){node.pre.next = node.next;node.next.pre = node.pre;}private void putFirst(Node node){node.next =  dummy.next;node.pre = dummy;dummy.next.pre = node;dummy.next = node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/