1. 題目

請你設計并實現一個滿足 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

2. 題解

class LRUCache {private final int capacity;private final Map<Integer,Integer>cache = new LinkedHashMap<>(); //內置LRUpublic LRUCache(int capacity){this.capacity = capacity;}public int get(int key) {//刪除key，并利用返回值判斷key是否在cache中Integer value = cache.remove(key);if(value != null){cache.put(key,value);return value;}return -1;}public void put(int key, int value) {////刪除key，并利用返回值判斷key是否在cache中if(cache.remove(key) != null){cache.put(key,value);return;}if (cache.size() == capacity){Integer eldestKey = cache.keySet().iterator().next();cache.remove(eldestKey);}cache.put(key,value);}
}/*** 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);*/

3. 解析

依舊出自這位老師：【圖解】一張圖秒懂 LRU！（Python/Java/C++/Go/JS/Rust）

1. public LRUCache(int capacity): 這是構造函數，當創建LRUCache的實例時會被調用。它設置了緩存的容量大小并初始化了一個LinkedHashMap來作為實際的緩存。

2. public int get(int key): 這個方法用于獲取指定鍵對應的值，如果緩存中不存在該鍵，則返回-1。它首先嘗試從緩存中刪除并重新插入鍵值對（如果存在于緩存中），然后再將新的鍵值對添加到緩存中。

3. public void put(int key, int value): 這個方法用于向緩存中插入一個新的鍵值對。它首先嘗試從緩存中刪除并重新插入鍵值對（如果存在于緩存中），然后再將新的鍵值對添加到緩存中。如果緩存已滿（即達到其容量大小），則會移除最近最少使用的元素（即最后一個被插入的元素）以釋放新的空間。