Description
Difficulty: 2.5/5.0
URL: https://oj.leetcode.com/problems/lru-cache/
Solution
This problem requires us to implement a LRU cache that supports two operations: get(int key) and set(int key, int val). An unodered_map would suffice for random access with keys and a doubly linked list can allow us to update the order of least recently used in time. We use unordered_map to reach the corresponding node in the list in constant time and the val is also saved in the node.
class LRUnode{
public:
LRUnode * next, * prev;
int val;
int key;
LRUnode(int key, int val){
this->key = key;
this->val = val;
next = prev = nullptr;
}
};
class LRUCache{
int capacity;
unordered_map<int, LRUnode *>cache;
LRUnode *head, *tail;
public:
LRUCache(int capacity) {
this->capacity = capacity;
tail = new LRUnode(-1, -1);
head = new LRUnode(-1, -1);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) != cache.end()){ //exist
update(key, cache[key]->val);
return cache[key]->val;
}
else
return -1;
}
void set(int key, int val) {
LRUnode *tp;
if (cache.find(key) == cache.end()){ //key not exist
if (!this->capacity){ //full
// remove the least used key at the beginning of the list
tp = head->next;
head->next = head->next->next;
head->next->prev = head;
cache.erase(tp->key);
tp->key = key;
tp->val = val;
}
else{ // not full
tp = new LRUnode(key, val);
this->capacity --;
}
// put the new key at the end
cache[key] = tp;
tp->next = tail;
tp->prev = tail->prev;
tail->prev->next = tp;
tail->prev = tp;
}
else // update existing key
update(key, val);
}
void update(int key, int val){
LRUnode * ptr = cache[key];
ptr->val = val;
//put it at the end of the list
ptr->prev->next = ptr->next;
ptr->next->prev = ptr->prev;
ptr->next = tail;
ptr->prev = tail->prev;
tail->prev->next = ptr;
tail->prev = ptr;
}
};