146. LRU Cache.md

146. LRU Cache

思路

题目要求设计一个最近最少使用（Least Recently Used, LRU）缓存。要求查询和插入都是O(1)，如果插入后容量超过最大容量则需要删除最近最少使用的一个，即删除元素也需O(1)。

由于时间复杂度限制为O(1)，所以肯定是要用hash，又因为我们需要删掉一个最不常用的元素，所以我们需要维护一个按照最近使用过的先后顺序的序列，这个序列要能在O(1)的时间复杂度在头部进行插入和在尾部进行删除，所以可以使用双向环形链表，即STL中的list。

综上，所以我们维护一个hashmap，存放key到list的迭代器的映射；还要维护一个存放value的list，其中的元素是一个pair(key, value)。

• get：在hashmap中查找对应list的迭代器，如果找到则需要将该元素移动到list头部（可以先删除再在头部插入或者直接使用STL中的splice）；
• put：现在hashmap中查找，如果找到了需要先删除原来的；再在list头部插入；最后检测是否超过最大容量，若是需要删除list尾部对应元素。

注意：

• 环形双向链表list的用法，如push_front、pop_back等。
• rbegin()返回容器最后一个元素的迭代器。
• l.splice (iterator position, list& x, iterator i)可以将list x的元素 i 插入到容器的position位置。

C++

class LRUCache {
private:
    int cap;
    list<pair<int,int>>values; // <key, value>
    unordered_map<int, list<pair<int,int>>::iterator>cache;
public:
    LRUCache(int capacity): cap(capacity){ } // 列表初始化
    
    int get(int key) {
        auto cache_iter = cache.find(key);
        if(cache_iter == cache.end()) return -1;
        else {
            auto value_iter = cache_iter -> second;
            int value = value_iter -> second;

            // values.splice(values.begin(), values, value_iter); // 也可以用下面三行代码
            values.erase(value_iter);
            values.push_front({key, value});
            cache[key] = values.begin();
            
            return value;            
        } 
    }
    
    void put(int key, int value) {
        auto cache_iter = cache.find(key);
        if(cache_iter != cache.end()) 
            values.erase(cache_iter -> second);

        values.push_front({key, value});
        cache[key] = values.begin();
        if(values.size() > cap){
            cache.erase(values.rbegin() -> first);
            values.pop_back();
        }
    }
};