Using linked list: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88class LinkedNode {
public:
LinkedNode *prev, *next;
int val;
LinkedNode(int val) {
this->val = val;
this->prev = nullptr;
this->next = nullptr;
}
};
class LinkedList {
private:
LinkedNode *head, *tail;
public:
LinkedList() {
this->head = nullptr;
this->tail = nullptr;
}
void erase(LinkedNode *p) {
if (p == tail) {
tail = tail->prev;
} else if (p == head) {
head = head->next;
}
if (p->prev) {
p->prev->next = p->next;
}
if (p->next) {
p->next->prev = p->prev;
}
}
LinkedNode *begin() { return head; }
LinkedNode *rbegin() { return tail; }
void push_front(int val) {
LinkedNode *node = new LinkedNode(val);
node->prev = nullptr;
node->next = head;
if (head) {
head->prev = node;
}
head = node;
if (tail == nullptr) {
tail = head;
}
}
void pop_back() { erase(tail); }
};
class LRUCache {
LinkedList lst;
unordered_map<int, LinkedNode *> key_to_node;
unordered_map<int, int> key_to_value;
int capacity;
public:
LRUCache(int capacity) { this->capacity = capacity; }
int get(int key) {
auto it = key_to_node.find(key);
if (it == key_to_node.end()) {
return -1;
}
int value = key_to_value[key];
put(key, value);
return value;
}
void put(int key, int value) {
auto it = key_to_node.find(key);
if (it != key_to_node.end()) {
lst.erase(it->second);
key_to_node.erase(key);
key_to_value.erase(key);
}
lst.push_front(key);
key_to_node[key] = lst.begin();
key_to_value[key] = value;
if (key_to_node.size() > capacity) {
LinkedNode *tail = lst.rbegin();
key_to_node.erase(tail->val);
key_to_value.erase(tail->val);
lst.pop_back();
}
}
};
Using STL: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36class LRUCache {
int capacity;
list<pair<int, int>> lst;
unordered_map<int, list<pair<int, int>>::iterator> mp;
public:
LRUCache(int capacity) {
this->capacity = capacity;
lst.clear();
mp.clear();
}
int get(int key) {
auto it = mp.find(key);
if (it == mp.end()) {
return -1;
}
int value = it->second->second;
put(key, value);
return value;
}
void put(int key, int value) {
auto keyToIter = mp.find(key);
if (keyToIter != mp.end()) {
lst.erase(keyToIter->second);
mp.erase(keyToIter);
}
lst.push_front({key, value});
mp[key] = lst.begin();
if (lst.size() > capacity) {
mp.erase(lst.rbegin()->first);
lst.pop_back();
}
}
};