/
solution.ts
95 lines (83 loc) · 2.39 KB
/
solution.ts
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
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Design #Linked_List
// #Doubly_Linked_List #Udemy_Linked_List #Big_O_Time_O(1)_Space_O(capacity)
// #2023_10_06_Time_473_ms_(94.72%)_Space_125.1_MB_(69.62%)
interface ICacheNode {
key: number
value: number
prev: ICacheNode | null
next: ICacheNode | null
}
class CacheNode implements ICacheNode {
public key: number
public value: number
public prev: ICacheNode
public next: ICacheNode
constructor(key: number, value: number, prev?: ICacheNode, next?: ICacheNode) {
this.key = key
this.value = value
this.prev = prev ?? null
this.next = next ?? null
}
}
class LRUCache {
private cache = new Map<number, CacheNode>()
private capacity
private head = new CacheNode(0, 0)
private tail = new CacheNode(0, 0)
constructor(capacity: number) {
this.capacity = capacity
this.head.next = this.tail
this.tail.prev = this.head
}
private append(node: CacheNode) {
const prev = this.tail.prev
this.tail.prev = node
node.next = this.tail
node.prev = prev
prev.next = node
}
private remove(node: CacheNode) {
const { prev, next } = node
prev.next = next
next.prev = prev
node.next = null
node.prev = null
return node
}
private promote(node: CacheNode) {
const removed = this.remove(node)
this.append(removed)
}
get(key: number): number {
if (!this.cache.has(key)) {
return -1
}
const node = this.cache.get(key)
this.promote(node)
return node.value
}
put(key: number, value: number): void {
let node
if (this.cache.has(key)) {
node = this.cache.get(key)
node.value = value
this.promote(node)
} else {
if (this.capacity === this.cache.size) {
const leastUsed = this.head.next
this.cache.delete(leastUsed.key)
this.remove(leastUsed)
}
node = new CacheNode(key, value)
this.append(node)
}
this.cache.set(key, node)
}
}
/*
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
export { LRUCache }