题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/e3769a5f49894d49b871c09cadd13a61
include
include
include
class Solution {
public:
/**
* lru design
* @param operators int整型vector<vector<>> the ops
* @param k int整型 the k
* @return int整型vector
*/
private:
list<pair<int ,int>> getList;
unordered_map<int, list<pair<int ,int>>::iterator> setList;
int capacity;
public:
void set(int key,int value)
{
auto iter= setList.find(key);
if( iter != setList.end())
{
getList.erase(setList[key]);
getList.push_front({key,value});
setList[key] = getList.begin();
}
else
{
if(getList.size() == capacity)
{
auto iter = setList.find(getList.back().first);
setList.erase(iter);
getList.pop_back();
}
getList.push_front({key,value});
setList[key] = getList.begin();
}
}
int get(int key)
{
if(setList.find(key) != setList.end()) { auto iter = setList[key]; getList.push_front(*iter); setList[key] = getList.begin(); getList.erase(iter); return setList[key] ->second; } else { return -1; } } vector<int> LRU(vector<vector<int> >& operators, int k) { // write code here vector<int> temp; if(k==0) return temp; capacity = k; for(int i=0; i< operators.size();i++) { if(operators[i][0] == 1) { if(operators[i][1] < (-2*pow(10,9)) || operators[i][1] > (2*pow(10,9))) continue; if(operators[i][2] < (-2*pow(10,9)) || operators[i][2] > (2*pow(10,9))) continue; set(operators[i][1],operators[i][2]); } else if(operators[i][0] == 2) { temp.push_back(get(operators[i][1])); } } return temp; }
};