set 和 get的时候要先看在不在hash表中,在的话,从list和hash表中移除,再重新添加进list头部和hash表。另外添加元素的时候要注意超过容量就从list尾部淘汰元素,并删除hash表中对应的元素。
stl list的iterator是可以保存的,List添加删除元素不会导致其他iterator失效。因为iterator指向List中元素
#include <unordered_map> #include <list> #include <vector> using namespace std; struct Node { Node(int k = 0, int v = 0) : key(k), val(v) {} int key; int val; }; 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 cap = k; vector<int> ans; for (auto &input : operators) { if (input[0] == 1) { set(input[1], input[2]); } else { ans.push_back(get(input[1])); } } return ans; } //删除 int remove(std::list<Node>::iterator &ite) { int key = ite->key; int val = ite->val; L.erase(ite); H.erase(key); return val; } // 添加 void add(int key, int val) { L.push_front(Node(key, val)); H[key] = L.begin(); if (L.size() > cap) { auto last = L.end(); --last; remove(last); } } void set(int x, int y) { auto ite = H.find(x); //已经存在,删除了再添加到头部 if (ite != H.end()) { remove(ite->second); } add(x, y); } int get(int x) { int val = 0; //已经存在,删除了再添加到头部 auto ite = H.find(x); if (ite != H.end()) { val = remove(ite->second); add(x, val); return val; } return -1; } private: std::list<Node> L; std::unordered_map<int, std::list<Node>::iterator> H; int cap; };