leetcode-146 - LRU Cache

動機

兩題很像，所以就一起寫

Problem

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.

The functions get and put must each run in O(1) average 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]ExplanationLRUCache 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 1lRUCache.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 3lRUCache.get(4);    // return 4

Constraints:

1 <= capacity <= 3000
0 <= key <= 10⁴
0 <= value <= 10⁵
At most 2 * 10⁵ calls will be made to get and put.

146: LRU Cache

為了讓get是O(1)，需要hash

為了符合LRU，就用Linked List，把最近使用的放到最上面，最下面的就是要被驅逐的key

這裡是用c++寫，因為python的Linked List，要自幹雖然說可以用deque模擬，但是沒辦法把node移到頂端，沒辦法操作reference，所以就改用C++的list來做了

class LRUCache {
private:
    list<int> l;
    int c;
    ordered_map<int, pair<list<int>::iterator, int>> m;
public:
    pair<list<int>::iterator, int>& moveToTop(int key) {
        auto& tmp = m[key];
        l.erase(std::get<0>(tmp));
        l.push_front(key);
        auto&& ret = make_pair(l.begin(), std::get<1>(tmp));
        m[key] = ret;
        return m[key];
    }

    LRUCache(int capacity): c(capacity) {
    }
    
    int get(int key) {
        auto tmp = m.find(key);
        if(tmp != m.end()) {
            auto& tmp = moveToTop(key);
            return std::get<1>(tmp);
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        auto exist = m.find(key);
        if (exist != m.end()) {
            auto& tmp = moveToTop(key);
            m[key] = std::move(make_pair(std::get<0>(tmp), value));
        } else {
            if(l.size() >= c) {
                int evict = l.back();
                m.erase(evict);
                l.pop_back();
            }
            l.push_front(key);
            m[key] = std::move(make_pair(l.begin(),value));
        }
        
    }
};

動機#

Problem#

146: LRU Cache#

動機

Problem

146: LRU Cache