题解 | #设计LRU缓存结构#

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    map<int, int> cache;
    list<int> li;
    vector<int> ret;
    int len = 0;
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        len = k;
        for (auto &ele : operators) {
            if (ele[0] == 1) {
                set(ele[1], ele[2]);
            } else {
                get(ele[1]);
            }
        }
        return ret;
    }
    void set(int k, int v) {
        auto iter = cache.find(k);
        if (iter != cache.end()) {
            li.remove(k);
            li.push_front(k);
            cache[k] = v;
        } else {
            if (cache.size() >= len) {
                cache.erase(cache.find(li.back()));
                li.pop_back();
            }
            li.push_front(k);
            cache[k] = v;
        }
    }
    void get(int k) {
        auto iter = cache.find(k);
        if (iter != cache.end()) {
            int v = iter->second;
            li.remove(k);
            li.push_front(k);
            ret.push_back(v);
        } else {
            ret.push_back(-1);
        }
    }
};