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