-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLRUCache.java
More file actions
88 lines (76 loc) · 2.07 KB
/
LRUCache.java
File metadata and controls
88 lines (76 loc) · 2.07 KB
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
public class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value, Node prev, Node next) {
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
}
class DLL {
public Node head;
public Node tail;
public DLL() {
this.head = new Node(-3, -3, null, null);
this.tail = new Node(-3, -3, this.head, null);
this.head.next = tail;
}
public void addFirst(Node first) {
first.next = this.head.next;
first.prev = this.head;
this.head.next.prev = first;
this.head.next = first;
}
public void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
public Node removeLast() {
if (tail.prev == this.head) return null; // empty
Node last = this.tail.prev;
remove(last);
return last;
}
}
class LRUCache {
Map<Integer, Node> cacheMap = new HashMap<>();
DLL dll = new DLL();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!cacheMap.containsKey(key)) {
return -1;
}
Node node = cacheMap.get(key);
this.dll.remove(node);
this.dll.addFirst(node);
return node.value;
}
public void put(int key, int value) {
if (cacheMap.containsKey(key)) {
Node node = this.cacheMap.get(key);
node.value = value;
this.dll.remove(node);
this.dll.addFirst(node);
} else {
if (cacheMap.size() == capacity) {
Node last = this.dll.removeLast();
cacheMap.remove(last.key);
}
Node newNode = new Node(key, value, null, null);
this.dll.addFirst(newNode);
cacheMap.put(key, newNode);
}
}
}
/**
* 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);
*/