Very easy C++ solution using queue and maps


#1

unordered_map<int,int> val;
unordered_map<int,int> tim;
int cap ;
int cnt;
int t;
queue<pair<int,int>> q;

LRUCache::LRUCache(int capacity) {
val.erase(val.begin(), val.end());
tim.erase(tim.begin(), tim.end());
cap = capacity;
cnt = 0;
t=0;
}

int LRUCache::get(int key) {
if(cnt>0){
auto it=tim.find(key);
if(it==tim.end()){
return -1;
}
tim[key]=t++;
q.push({key,tim[key]});
return val[key];
}
return -1;
}

void LRUCache::set(int key, int value) {
auto it=tim.find(key);
if(it!=tim.end()){
tim[key]=t++;
val[key]=value;
q.push({key,tim[key]});
}
else{
if(cnt<cap){
val[key]=value;
tim[key]=t++;
q.push({key,tim[key]});
cnt++;
}
else{
while(!q.empty() && (tim.find(q.front().first)==tim.end() || tim[q.front().first]!=q.front().second)){
q.pop();
}
if(!q.empty()){
pair<int,int> p=q.front();
q.pop();
tim.erase(p.first);
val.erase(p.first);
cnt–;
}
val[key]=value;
tim[key]=t++;
q.push({key,tim[key]});
cnt++;
}
}
}