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
| package main
import "fmt"
type LRUCache struct {
limit int
hashMap map[int]*Node
head *Node
tail *Node
}
type Node struct {
key int
val int
pre *Node
next *Node
}
func NewNode(k, v int) *Node {
return &Node{
key: k,
val: v,
}
}
func NewLRUCache(cap int) LRUCache {
c := LRUCache{
limit: cap,
hashMap: make(map[int]*Node),
head: NewNode(0, 0),
tail: NewNode(0, 0),
}
c.head.next = c.tail
c.tail.pre = c.head
return c
}
func (c *LRUCache) Get(key int) int {
if node, ok := c.hashMap[key]; ok {
c.moveToHead(node)
return node.val
}
return -1
}
func (c *LRUCache) Put(k, v int) {
if node, ok := c.hashMap[k]; !ok {
if len(c.hashMap) >= c.limit {
tail := c.removeTail()
delete(c.hashMap, tail.key)
}
node = NewNode(k, v)
c.hashMap[k] = node
c.addToHead(node)
} else {
node.val = v
c.moveToHead(node)
}
}
func (c *LRUCache) moveToHead(node *Node) {
c.removeNode(node)
c.addToHead(node)
}
func (c *LRUCache) removeNode(node *Node) {
node.pre.next = node.next
node.next.pre = node.pre
}
func (c *LRUCache) removeTail() *Node {
tail := c.tail.pre
c.removeNode(tail)
return tail
}
func (c *LRUCache) addToHead(node *Node) {
node.pre = c.head
node.next = c.head.next
c.head.next.pre = node
c.head.next = node
}
func main() {
cache := NewLRUCache(3)
cache.Put(1,1)
cache.Put(2,2)
cache.Put(3,3)
cache.Put(4,4)
fmt.Println(cache.Get(3))
}
|
