-
Notifications
You must be signed in to change notification settings - Fork 0
/
Dailyleet
73 lines (59 loc) · 1.5 KB
/
Dailyleet
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
class LRUCache {
class Node {
int key;
int val;
Node prev;
Node next;
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
Node head = new Node(-1, -1);
Node tail = new Node(-1, -1);
int cap;
HashMap<Integer, Node> m = new HashMap<>();
public LRUCache(int capacity) {
cap = capacity;
head.next = tail;
tail.prev = head;
}
private void addNode(Node newnode) {
Node temp = head.next;
newnode.next = temp;
newnode.prev = head;
head.next = newnode;
temp.prev = newnode;
}
private void deleteNode(Node delnode) {
Node prevv = delnode.prev;
Node nextt = delnode.next;
prevv.next = nextt;
nextt.prev = prevv;
}
public int get(int key) {
if (m.containsKey(key)) {
Node resNode = m.get(key);
int ans = resNode.val;
m.remove(key);
deleteNode(resNode);
addNode(resNode);
m.put(key, head.next);
return ans;
}
return -1;
}
public void put(int key, int value) {
if (m.containsKey(key)) {
Node curr = m.get(key);
m.remove(key);
deleteNode(curr);
}
if (m.size() == cap) {
m.remove(tail.prev.key);
deleteNode(tail.prev);
}
addNode(new Node(key, value));
m.put(key, head.next);
}
}