本文共 1419 字,大约阅读时间需要 4 分钟。
示例1 输入 [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3 返回值 [1,-1]说明 第一次操作后:最常使用的记录为("1", 1) 第二次操作后:最常使用的记录为("2", 2),("1", 1)变为最不常用的 第三次操作后:最常使用的记录为("3", 2),("1", 1)还是最不常用的 第四次操作后:最常用的记录为("1", 1),("2", 2)变为最不常用的 第五次操作后:大小超过了3,所以移除此时最不常使用的记录("2", 2),加入记录("4", 4),并且为最常使用的记录,然后("3", 2)变为最不常使用的记录
class Solution { private:public: /** * lru design * @param operators int整型vector<>> the ops,操作数 * @param k int整型 the k ,LRU缓存大小为k * @return int整型vector */ int capacity; list > lrulst;//链表 //list >::iterator 指向里面的元素 unordered_map >::iterator > lruhash;//map vector LRU(vector >& operators, int k) { // write code here vector res; capacity = k; for(auto opt : operators){ switch (opt[0]){ case 1: set(opt[1],opt[2]); break; case 2: res.push_back(get(opt[1])); break; default: break; } } return res; } void set(int key,int val){ auto iter = lruhash.find(key); //判断是否存在 if(iter == lruhash.end()) { //如果容积满了 if(capacity == lrulst.size()) { //删掉最末元素 lruhash.erase(lrulst.back().first); lrulst.pop_back(); } } else lrulst.erase(iter->second);//删掉更新一下 //更新 lrulst.push_front({ key,val}); lruhash[key] = lrulst.begin(); } int get(int key){ auto iter = lruhash.find(key); if(iter == lruhash.end()) return -1; int val = iter->second->second; //删掉链表节点,再重新添加 lrulst.erase(iter->second); lrulst.push_front(*iter->second); return val; }};
转载地址:http://qzevi.baihongyu.com/