146. LRU Cache

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
 

Constraints:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
At most 3 * 104 calls will be made to get and put.

这题让我们实现一个LRU缓存，当满了之后，需要把最不常用的给释放，然后又有时间复杂度的需求。

所以我们使用map和list来实现，map存key和指向list元素的迭代器。list保存着kv pair。当使用的时候，把对应list里的kv对移动到开头，弹出的时候清理map和list即可。

这里主要利用了list增删元素O(1)的特点，还有hash表常数查找时间的特点。

class LRUCache : public Solution {
public:
    void Exec() {

    }

    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = dict.find(key);
        if (it == dict.end()) {
            return -1;
        }
        int value = it->second->second;
        kvs.erase(it->second);
        kvs.push_front(std::make_pair(key, value));
        dict[key] = kvs.begin();
        return value;
    }
    
    void put(int key, int value) {
        auto it = dict.find(key);
        if (it == dict.end()) {
            kvs.push_front(std::make_pair(key, value));
            dict[key] = kvs.begin();

            if (kvs.size() > cap) {
                int backKey = kvs.back().first;
                dict.erase(backKey);
                kvs.pop_back();
            }
        } else {
            kvs.erase(it->second);
            kvs.push_front(std::make_pair(key, value));
            dict[key] = kvs.begin();
        }
    }

    int cap;
    list<std::pair<int, int>> kvs;
    unordered_map<int, list<std::pair<int, int>>::iterator> dict;
};