LeetCode Daily Question 12

Mar 17th 2022

3 月 17 日 每日一题

题目：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.
The functions get and put must each run in O(1) average time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

思路

这道题出现的时间很合适，刚好 370 讲到 Cache。
本题的思路是使用一个 list 存储 key/value pairs，通过对 pair 位置的调整，以实现 front 为 most recently used，back 为 least recently used。
为了达到 O（1）的 search，我们还需要用一个 hashmap 存储指向每一个 pair 的 iterator，并以 pair 的 key 作为 hashmap 的 key。
实现时通过 splice 将一个 node 移动到 list 的 front。put 可以分为三种情况：exit， not exit && full 和 not exit & not full。顺便 map 的 erase 既可以使用 iterator，也可以直接用 key。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> cacheMap;
public:
    LRUCache(int capacity):capacity{capacity} {}

    int get(int key) {
        if(cacheMap.find(key) == cacheMap.end())
            return -1;
        //move to the front
        cache.splice(cache.begin(), cache, cacheMap.find(key)->second);
        return cacheMap.find(key)->second->second;
    }

    void put(int key, int value) {
        pair<int, int> temp{key, value};
        if(cacheMap.find(key) != cacheMap.end()){
            cacheMap[key]->second = value;
            //move to the front
            cache.splice(cache.begin(), cache, cacheMap.find(key)->second);
            return;
        }
        else if(cacheMap.size() == capacity){
            //delete least recently
            cacheMap.erase(cache.back().first);
            cache.pop_back();
        }
        //add
        cache.push_front(temp);
        cacheMap[key] = cache.begin();
    }
};
,
  1. 3 月 17 日 每日一题
    1. 题目：146. LRU Cache
    2. 思路
    3. 代码