-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-460-LFU-Cache.java
148 lines (119 loc) · 4.53 KB
/
LeetCode-460-LFU-Cache.java
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
// 1. My Own Implementation, Wrong Answer
/*
["LFUCache","put","put","put","put","get","get","get","get","put","get","get","get","get","get"]
[[3],[1,1],[2,2],[3,3],[4,4],[4],[3],[2],[1],[5,5],[1],[2],[3],[4],[5]]
Output:
[null,null,null,null,null,4,3,2,-1,null,-1,2,-1,4,5]
Expected:
[null,null,null,null,null,4,3,2,-1,null,-1,2,3,-1,5]
*/
// class LFUCache {
// HashMap<Integer, Integer> map;
// PriorityQueue<Integer> pq;
// HashMap<Integer, Integer> keyToVal;
// int capacity;
// public LFUCache(int capacity) {
// map = new HashMap<>();
// pq = new PriorityQueue<>((a, b) -> map.getOrDefault(a, 0) - map.getOrDefault(b, 0));
// keyToVal = new HashMap<>();
// this.capacity = capacity;
// }
// public int get(int key) {
// // System.out.println(keyToVal.toString());
// // System.out.println(map.toString());
// // System.out.println(pq.toString());
// // System.out.println(" ");
// if (!keyToVal.containsKey(key)) return -1;
// map.put(key, map.getOrDefault(key, 0) + 1);
// pq.remove(key);
// pq.offer(key);
// return keyToVal.get(key);
// }
// public void put(int key, int value) {
// if (capacity == 0) return;
// if (keyToVal.containsKey(key)) {
// keyToVal.put(key, value);
// map.put(key, map.getOrDefault(key, 0) + 1);
// pq.remove(key);
// pq.offer(key);
// return;
// }
// while (pq.size() >= capacity) {
// int k = pq.poll();
// map.remove(k);
// keyToVal.remove(k);
// }
// map.put(key, map.getOrDefault(key, 0) + 1);
// pq.offer(key);
// keyToVal.put(key, value);
// // System.out.println(keyToVal.toString());
// // System.out.println(map.toString());
// // System.out.println(pq.toString());
// // System.out.println(" ");
// }
// }
/*
https://leetcode.com/problems/lfu-cache/discuss/94521/JAVA-O(1)-very-easy-solution-using-3-HashMaps-and-LinkedHashSet
At first I didn't understand why we didn't need to care about nextMin and we just could add 1 to min. Now it makes sense that min will always reset to 1 when adding a new item. And also, min can never jump forward more than 1 since updating an item only increments it's count by 1.
*/
class LFUCache {
HashMap<Integer, Integer> keyToVal;
HashMap<Integer, Integer> keyToCount;
HashMap<Integer, LinkedHashSet<Integer>> countToKeys;
int capacity;
int minCount;
public LFUCache(int capacity) {
keyToVal = new HashMap<>();
keyToCount = new HashMap<>();
countToKeys = new HashMap<>();
this.capacity = capacity;
this.minCount = Integer.MAX_VALUE;
}
public int get(int key) {
if (!keyToVal.containsKey(key)) return -1;
// Update count in keyToCount and countToKeys
int count = keyToCount.getOrDefault(key, 0);
removeCount(key);
putCount(key, count + 1);
return keyToVal.get(key);
}
public void put(int key, int value) {
if (capacity <= 0) return;
if (keyToVal.containsKey(key)) {
keyToVal.put(key, value);
get(key); // get key to update the count
return;
}
if (keyToVal.size() >= capacity) {
int minKey = countToKeys.get(minCount).iterator().next();
keyToVal.remove(minKey);
removeCount(minKey);
}
minCount = 1;
keyToVal.put(key, value);
get(key);
}
private void putCount(int key, int count) {
keyToCount.put(key, count);
countToKeys.computeIfAbsent(count, k -> new LinkedHashSet<>()).add(key);
}
private void removeCount(int key) {
if (!keyToCount.containsKey(key)) return;
int count = keyToCount.get(key);
keyToCount.remove(key);
countToKeys.get(count).remove(key);
// Remove countToKeys entry if LinkedHashSet keys are empty (not necessary actually), Update minCount if necessary
if (countToKeys.get(count).size() == 0) {
countToKeys.remove(count);
if (count == minCount) {
minCount++;
}
}
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/