class LRUCache{
public:
list<vector<int> > _list;
unordered_map<int, list<vector<int> >::iterator> _hash;
int _capacity;
LRUCache(int capacity): _capacity(capacity) {
}
int get(int key) {
if(_hash.count(key) > 0) {
auto it = _hash[key];
vector<int> temp(*it);
_list.erase(it);
_list.push_front(temp);
_hash[key] = _list.begin();
return temp[1];
} else {
return -1;
}
}
void set(int key, int value) {
if(_hash.count(key) > 0) {
auto it = _hash[key];
_list.erase(it);
_list.push_front(vector<int>{key, value});
_hash[key] = _list.begin();
} else {
if(_hash.size() >= _capacity) {
vector<int> temp(_list.back());
_list.pop_back();
_hash.erase(temp[0]);
}
vector<int> newElement{key, value};
_list.push_front(newElement);
_hash.emplace(key, _list.begin());
}
}
};
5/18/2014
Leetcode -- LRU Cache
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment