LeetCode_資料結構設計_中等_146. LRU 緩存

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

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
           

提示：

1 <= capacity <= 3000

0 <= key <= 10000

0 <= value <= 105

最多調用 2 * 105 次 get 和 put

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/lru-cache

2.思路

（1）哈希連結清單

思路參考算法就像搭樂高：帶你手撸 LRU 算法。

3.代碼實作（Java）

//思路1————哈希連結清單
class LRUCache {
    
    //定義哈希連結清單
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    //cache 的容量
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        } else {
            //将該 key 變為最近使用
            makeRecently(key);
            return cache.get(key);
        }
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            //key 已經存在，修改其對應的資料值 value
            cache.put(key, value);
            //将 key 變為最近使用
            makeRecently(key);
            return;
        }
        if (cache.size() >= this.capacity) {
            //容量已滿，連結清單頭部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        //将新的 key 添加到連結清單尾部
        cache.put(key, value);
    }

    public void makeRecently(int key) {
        int val = cache.get(key);
        //删除 key
        cache.remove(key);
        //将其重新添加到連結清單尾部
        cache.put(key, val);
    }
}

/**
 * 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);
 */