LeetCode 146. LRU Cache [Medium] [C++] 解題筆記

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

Follow up:
Could you do get and put in O(1) time complexity?

 

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

想法:

    這題是一個資料結構實作題，要我們實作一個 Least Recently Used cache，顧名思義就是maintain一個 list 其中

包含 capacity 個最近存取的內容，並要求 get (query) 和 put (set)操作都需要在 O(1) time 內完成。

為了要在常數時間內完成兩項操做我們需要利用 hashmap 來當作查找表，同時維持一個 list 來當作 cache，list 中存放實際

的資料而 hashmap 中存放 key -> list::iterator 的 mapping，方便我們利用 key 值快速找到對應的 list node。

完整程式碼:

解法一:(use splice method in list)
/* O(1) get and put
 * double linked list(list in STL) and unordered_map
 */
class LRUCache {
public:
    int max_size;
    // key, value
    list<pair<int, int>> cache;
    // key, iterator point to corresponding node in list
    unordered_map<int, list<pair<int, int>>::iterator> m;
    LRUCache(int capacity) {   
        max_size = capacity;
    }
    
    int get(int key) {
        const auto it = m.find(key);
        if (it == m.end()) { return -1; }
        // Move this key to the front of the cache
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        const auto it = m.find(key);
        // key exist
        if (it != m.end()) {
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        // key doesn't exist
        if (m.size() == max_size) {
            const auto& cur = cache.back();
            m.erase(cur.first);
            cache.pop_back();
        }
        // add new (key, value) pair to the front of list and update mapping
        cache.push_front(make_pair(key, value));
        m[key] = cache.begin();
    }   
};

解法二:
class LRUCache {
public:
    int max_size;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> m;
    LRUCache(int capacity) {
        max_size = capacity;
    }
    
    int get(int key) {
        auto it = m.find(key);
        if (it == m.end()) { return -1; }
        int value = it->second->second;
        cache.erase(it->second);
        cache.push_front(make_pair(key, value));
        m[key] = cache.begin();
        return cache.front().second;
    }
    
    void put(int key, int value) {
        const auto it = m.find(key);
        if (it != m.end()) {
            cache.erase(it->second);
            cache.push_front(make_pair(key, value));
            m[key] = cache.begin();
            return;
        }
        if (m.size() == max_size) {
            const auto& cur = cache.back();
            m.erase(cur.first);
            cache.pop_back();
        }
        cache.push_front(make_pair(key, value));
        m[key] = cache.begin();
        return;
    }
};
/**
 * 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);
 */