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

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        int num=0;
        map<int, int> m;
        list<int> l;
        vector<int> res;
        for(vector<vector<int>>::iterator it=operators.begin();it!=operators.end();it++)
        {
            if((*it).at(0)==1)
            {
                if(num<k)
                {
                    map<int,int>::iterator itt = m.find((*it).at(1));
                    if(itt!=m.end())
                    {
                        m.erase(itt);
                    }
                    m.insert(pair<int,int>((*it).at(1),(*it).at(2)));
                    l.push_back((*it).at(1));
                    num++;
                }
                else
                {
                    m.insert(pair<int,int>((*it).at(1),(*it).at(2)));
                    l.pop_front();
                    l.push_back((*it).at(1));
                }
            }
            if((*it).at(0)==2)
            {
                map<int,int>::iterator iter1;
                iter1 = m.find((*it).at(1));
                list<int>::iterator iter = l.end();
                for(list<int>::iterator vit=l.begin();vit!=l.end();vit++)
                {
                    if(*vit==(*it).at(1))
                    {
                        iter=vit;
                    }
                }
                if(iter!=l.end())
                {
                    res.push_back(iter1->second);
                    l.erase(iter);
                    
                    l.push_back((*it).at(1));
                }
                else
                {
                    res.push_back(-1);
                }
            }
        }
        return res;
    }
};