-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlruCache.go
86 lines (76 loc) · 1.68 KB
/
lruCache.go
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
//go:build ignore
package main
import "fmt"
type Node struct {
Key, Value int
Prev, Next *Node
}
type LRUCache struct {
Capacity int
Cache map[int]*Node
Left, Right *Node
}
func Constructor(capacity int) LRUCache {
lru := LRUCache{
Capacity: capacity,
Cache: make(map[int]*Node),
Left: &Node{},
Right: &Node{},
}
lru.Left.Next = lru.Right
lru.Right.Prev = lru.Left
return lru
}
func (this *LRUCache) remove(node *Node) {
next, prev := node.Next, node.Prev
prev.Next = next
next.Prev = prev
}
func (this *LRUCache) insert(node *Node) {
prev, next := this.Right.Prev, this.Right
prev.Next = node
next.Prev = node
node.Next = next
node.Prev = prev
}
func (this *LRUCache) get(key int) int {
if node, exist := this.Cache[key]; exist {
this.remove(node)
this.insert(node)
return node.Value
}
return -1
}
func (this *LRUCache) put(key, val int) {
if node, exist := this.Cache[key]; exist {
this.remove(node)
delete(this.Cache, key)
}
node := &Node{Key: key, Value: val}
this.Cache[key] = node
this.insert(node)
if len(this.Cache) > this.Capacity {
lru := this.Left.Next
this.remove(lru)
delete(this.Cache, lru.Key)
}
}
func main() {
commands := []string{"LRUCache", "put", "get", "put", "put", "get", "get"}
args := [][]int{{2}, {1, 10}, {1}, {2, 20}, {3, 30}, {2}, {1}}
var lru LRUCache
result := []interface{}{nil}
for i := 0; i < len(commands); i++ {
switch commands[i] {
case "LRUCache":
lru = Constructor(args[i][0])
result = append(result, nil)
case "put":
lru.put(args[i][0], args[i][1])
result = append(result, nil)
case "get":
result = append(result, lru.get(args[i][0]))
}
}
fmt.Println(result[1:])
}