LRU 优化

原题是 146. LRU缓存机制

这道题七个月前做过，当时勉强过了，就没有想太多，结果今天的每日一题又是这哥，本来准备拿出来直接提交一下，居然，超时了。。。。

先贴一下七个月前的实现，欢迎鞭尸，大家可以先看看问题到底出来哪里，晚一点我贴一下优化后的代码

class LRUCache {
public:
    int cap = 0;
    struct v {
        int key;
        int value;
    };
    list<v> q;
    LRUCache(int capacity) {
       cap = capacity;
    }
    
    int get(int key) {
        list<v>::iterator iter;
        v temp = {0, 0};
        bool find = false;
        for (iter = q.begin(); iter != q.end(); iter++)
        {
            if ((*iter).key == key)
            {
                temp.key = key;
                temp.value = (*iter).value;
                q.erase(iter);
                find = true;
                break;
            }
        }
        if (!find) {
            return -1;
        }
        q.push_front(temp);
        return temp.value;
    }
    
    void put(int key, int value) {
        v t = {0, 0};
        list<v>::iterator iter;
        for (iter = q.begin(); iter != q.end(); iter++)
        {
            if ((*iter).key == key)
            {
                t.key = key;
                t.value = value;
                q.erase(iter);
                q.push_front(t);
                return;
            }
        }
        
        if(q.size()+1 > cap) {
            q.pop_back();
        }
    
        v temp = {key, value};
        q.push_front(temp);
    }
};

今天看了一下，七个月前写的啥代码，v是个啥啊。。。。这类型命名，好像打一顿七个月前的我，哎。

可能大家一看，就能发现我的问题是每次在空间耗尽或者get的时候都要去for循环我的链表，那么对于这种快速查找的需求，那毫无疑问就是使用哈希，然而我当下还一时没有反应过来，还在别人的提示下才想到，惭愧

class LRUCache {
public:
    struct info {
        int key;
        int value;
    };

    list<info> infos;
    using infoIter = list<info>::iterator;
    unordered_map<int, infoIter> searchMap;

    LRUCache(int capacity) : capacity(capacity) {

    }

    int get(int key) {
        if (searchMap.find(key) == searchMap.end()) return -1;

        info temp = {(searchMap[key])->key, (searchMap[key])->value};
        infos.erase(searchMap[key]);
        infos.push_front(temp);
        searchMap[key] = infos.begin();

        return searchMap[key]->value;
    }

    void put(int key, int value) {
        if (infos.size() == capacity && searchMap.find(key) == searchMap.end()) {
            auto temp = infos.rbegin()->key;
            infos.erase(searchMap[temp]);
            searchMap.erase(temp);
        }
        
        if (searchMap.find(key) != searchMap.end()) {
            infos.erase(searchMap[key]);
        }

        infos.push_front({key, value});
        searchMap[key] = infos.begin();
    }

private:
    int capacity;
};

最后，其实我一开始写的时候用的是map，突然想想我应该用哈希map，这样我又可以省去排序的复杂度啦，另外using 真好用，欢迎体验。