-
Notifications
You must be signed in to change notification settings - Fork 1
/
04.lru_cache.cpp
74 lines (71 loc) · 1.64 KB
/
04.lru_cache.cpp
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
// https://leetcode.com/problems/lru-cache/
class Node{
public:
int key;
int val;
Node* next;
Node* prev;
Node(int key, int val) {
this->key = key;
this->val = val;
this->prev = NULL;
this->next = NULL;
}
};
class LRUCache {
public:
Node* head = new Node(-1, -1);
Node* tail = new Node(-1, -1);
map<int, Node*> m;
int cap;
LRUCache(int capacity) {
this->cap = capacity;
head->next = tail;
tail->prev = head;
}
void addNode(Node* node) {
Node* next = head->next;
head->next = node;
node->prev = head;
next->prev = node;
node->next = next;
}
void removeNode(Node* node) {
Node* next = node->next;
Node* prev = node->prev;
next->prev = prev;
prev->next = next;
}
int get(int key) {
if (m.find(key) == m.end()) {
return -1;
}
Node* t = m[key];
m.erase(key);
removeNode(t);
addNode(t);
m[key] = t;
return t->val;
}
void put(int key, int value) {
if (m.find(key) == m.end()) {
if (cap == m.size()) {
m.erase(tail->prev->key);
removeNode(tail->prev);
}
} else {
Node* n = m[key];
m.erase(key);
removeNode(n);
}
Node* t = new Node(key, value);
addNode(t);
m[key] = t;
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/