-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_146.java
More file actions
114 lines (92 loc) · 3.04 KB
/
Copy pathP_146.java
File metadata and controls
114 lines (92 loc) · 3.04 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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package leetcode.medium;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class P_146 {
static class LRUCacheLHM {
Map<Integer, Integer> cache;
LRUCacheLHM(int capacity) {
cache = new LinkedHashMap<>(capacity, 0.75f, true) {
private static final long serialVersionUID = 316458002587273807L;
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
static class LRUCache {
static class ListNode {
ListNode prev;
ListNode next;
int key;
int val;
ListNode(int key, int val) {
this.key = key;
this.val = val;
}
static void moveToHead(ListNode node, ListNode head) {
removeNode(node);
addNode(node, head);
}
static void addNode(ListNode node, ListNode head) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
static ListNode popTail(ListNode tail) {
final ListNode prev = tail.prev;
removeNode(prev);
return prev;
}
static void removeNode(ListNode node) {
final ListNode prev = node.prev;
final ListNode next = node.next;
prev.next = next;
next.prev = prev;
}
}
Map<Integer, ListNode> map = new HashMap<>();
ListNode head = new ListNode(-1, -1);
ListNode tail = new ListNode(-1, -1);
int capacity;
int size;
LRUCache(int capacity) {
head.next = tail;
tail.prev = head;
this.capacity = capacity;
}
public int get(int key) {
final ListNode listNode = map.get(key);
if (listNode == null) {
return -1;
}
ListNode.moveToHead(listNode, head);
return listNode.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
final ListNode listNode = map.get(key);
listNode.val = value;
ListNode.moveToHead(listNode, head);
} else {
if (size == capacity) {
final ListNode listNode = ListNode.popTail(tail);
map.remove(listNode.key);
size--;
}
final ListNode listNode = new ListNode(key, value);
ListNode.addNode(listNode, head);
map.put(key, listNode);
size++;
}
}
}
}