-
-
Notifications
You must be signed in to change notification settings - Fork 420
/
LRU-Cache.cpp
104 lines (84 loc) · 2.43 KB
/
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// Here I am using a hashmap to store a node pointer by a key. It will give us O(1) for all operations.
class LRUCache {
private:
struct Node {
Node *left = nullptr;
Node *right = nullptr;
int key;
int value;
Node(int key, int value) : key(key), value(value) {}
};
Node *root = nullptr;
Node *tail = nullptr;
unordered_map<int, Node*> hashmap;
int capacity;
void update_root(Node *node) {
Node *tmp = root;
if (tail == nullptr) {
tail = node;
} else if (tail == node) {
tail = node;
if (node->left != nullptr) {
tail = node->left;
}
}
if (root == nullptr) {
root = node;
tmp = root;
return;
}
if (root != node) {
Node *t = node->left;
if (t != nullptr) {
t->right = node->right;
if (node->right != nullptr) {
node->right->left = t;
}
}
node->right = root;
root->left = node;
root = node;
}
}
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
if (hashmap.count(key) == 0) {
return -1;
} else {
Node *node = hashmap[key];
update_root(node);
return root->value;
}
}
void put(int key, int value) {
if ((int) hashmap.size() == capacity && hashmap.count(key) == 0) {
hashmap.erase(tail->key);
Node *new_tail = nullptr;
if (tail->left != nullptr) {
new_tail = tail->left;
}
tail->left = nullptr;
tail = nullptr;
tail = new_tail;
if (tail != nullptr) {
tail->right = nullptr;
}
}
Node *node;
if (hashmap.count(key) == 0) {
node = new Node(key, value);
} else {
node = hashmap[key];
}
node->value = value;
hashmap[key] = node;
update_root(node);
}
};
/**
* 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);
*/