https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked

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

小米一面，沒刷過題所以栽了，靜下來心看看解決方案

題解

題目中涉及到了 查詢、插入和刪除都要平均時間復雜度O(1)，查詢想要時間復雜度O(1) 可以用數組，插入刪除如果使用數組無法滿足要求，因為從數組中刪除元素涉及到元素的移動復雜度 O(n), 我們必須使用鏈表來插入和刪除，鏈表分為單鏈表和雙鏈表，如果使用單鏈表刪除元素的話還是需要遍歷才能找到前后的元素，所以我們使用 哈希表查詢 + 雙鏈表操作 的思路

通過設置head和tail虛節點，避免判空等處理，這樣取第一個元素時直接調用 head.next ，取最后一個元素時直接調用 tail.pre

class LRUCache {class Node {int val;int key;Node next;Node pre;public Node(int key, int val) {this.key = key;this.val = val;}}private int mSize;private Map<Integer, Node> map;private Node head;private Node tail;public LRUCache(int size) {mSize = size;map = new HashMap<>();// 技巧處，使用頭尾虛節點來處理 空異常head = new Node(-1, -1);tail = new Node(-1, -1);head.next = tail;tail.pre = head;}public int get(int key) {if (!map.containsKey(key)) return -1;Node node = map.get(key);removeNode(node);addToHead(node);return node.val;}public void put(int key, int val) {if (map.containsKey(key)) {removeNode(map.get(key));}Node node = new Node(key, val);map.put(key, node);addToHead(node);// 易錯點，超過限制時需要同時移除 雙鏈表 node和 map中的nodeif(map.size() > mSize){Node lastNode = tail.pre;removeNode(lastNode);map.remove(lastNode.key);}}private void addToHead(Node node) {Node first = head.next;head.next = node;node.next = first;first.pre = node;node.pre = head;}private void removeNode(Node node) {Node preNode = node.pre;Node nextNode = node.next;preNode.next = nextNode;nextNode.pre = preNode;}
}