先來(lái)看LRU Cache，LRU Cache的重點(diǎn)就是建立一個(gè) map<key, list<>::iterator> 的hash table。key存需要找的key，value是list的iterator。

而這個(gè)list<pair<int, int>> 存的就是key value pair。在get或set時(shí)，要把這個(gè)<key, value> pair 從當(dāng)前位置，放到棧頂。這個(gè)是用list.splice函數(shù)實(shí)現(xiàn)的。splice函數(shù)的用法如下：

list.splice(position, list name, list iterator)
lst.splice(lst.begin(), lst, it);

注意：在這里統(tǒng)一一下，無(wú)論LRU還是LFU Cache, 一律先刪，再加。

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(!mp.count(key)) return -1;
        auto it = mp[key];
        lst.splice(lst.begin(), lst, it);
        mp[key] = lst.begin();
        return it->second;
    }
    
    void put(int key, int value) {
        if(get(key) != -1){
            mp[key]->second = value;
        }
        else{
            if(lst.size() == capacity){
                auto it = lst.back();
                lst.pop_back();
                mp.erase(it.first);
            }
            lst.push_front({key, value});
            mp[key] = lst.begin();

        }
    }
private:
    int capacity;
    list<pair<int, int>> lst;
    unordered_map<int, list<pair<int, int>>::iterator> mp;
};

LFU Cache則要復(fù)雜不少，具體參考grandyang的LFU solution：
http://www.cnblogs.com/grandyang/p/6258459.html

LFU Cache的經(jīng)典solution是用doubly linkded list (http://dhruvbird.com/lfu.pdf)，上文解法用三個(gè)Hashmap模擬了這個(gè)doubly linked list，非常巧妙. 另外trick是在set時(shí)調(diào)用get，并討論考慮get != -1的情況. 本文變化是當(dāng)capacity reach full時(shí)，將隊(duì)尾pop出去. 注意，第一個(gè)keyValue Hashmap: key => {value, frequency}

純O(1)的solution：

class LFUCache {
public:
    LFUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if(!keyValue.count(key)) return -1;
        auto it = locator[key];
        frequency[keyValue[key].second++].erase(it);
        frequency[keyValue[key].second].push_front(key);
        locator[key] = frequency[keyValue[key].second].begin();
        if(frequency[minFreq].empty()) minFreq++;
        return keyValue[key].first;
        
    }
    
    void put(int key, int value) {
        if(cap <= 0) return;
        if(get(key) != -1){
            keyValue[key].first = value;
        }else{
            if(keyValue.size() == cap){
                int temp = frequency[minFreq].back();
                frequency[minFreq].pop_back();
                locator.erase(temp);
                keyValue.erase(temp);
            }
            keyValue[key] = {value, 1};
            frequency[1].push_front(key);
            locator[key] = frequency[1].begin();
            minFreq = 1;
        }
    }
private:
    int cap, minFreq;
    unordered_map<int, pair<int, int>> keyValue;
    unordered_map<int, list<int>> frequency;
    unordered_map<int, list<int>::iterator> locator;
};

簡(jiǎn)單一點(diǎn)的solution，不O(1), 但是省掉了一個(gè)HashMap，直接用list.remove(key)

class LFUCache {
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if(!keyValue.count(key)) return -1;
        frequency[keyValue[key].second++].remove(key);
        frequency[keyValue[key].second].push_front(key);
        if(frequency[minFreq].empty()) minFreq++;
        return keyValue[key].first;
    }
    
    void put(int key, int value) {
        if(capacity <= 0) return;
        if(get(key) != -1){
            keyValue[key].first = value;
        }
        else{
            if(keyValue.size() == capacity){
                int temp = frequency[minFreq].back();
                frequency[minFreq].pop_back();
                keyValue.erase(temp);
            }
            keyValue[key] = {value, 1};
            frequency[1].push_front(key);
            minFreq = 1;
        }
    }
private:
    int capacity, minFreq = 0;
    unordered_map<int, pair<int, int>> keyValue;
    unordered_map<int, list<int>> frequency;
};