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
|
type LFUCache struct {
cache map[int]*Node //Node 链表节点，存储数据k v以及频次freq和前后链表指针
freq map[int]*DoubleList //频次map，通过最小频次minFreq获取最少范问节点
ncap, size, minFreq int
}
func Constructor(capacity int) LFUCache {
return LFUCache{
cache: make(map[int]*Node),
freq: make(map[int]*DoubleList),
ncap: capacity,
}
}
func (this *LFUCache) Get(key int) int {
if node, ok := this.cache[key]; ok {
//节点存在，则需要新增频次操作
this.IncFreq(node)
return node.val
}
return -1
}
func (this *LFUCache) Put(key, value int) {
if this.ncap == 0 {
return
}
if node, ok := this.cache[key]; ok {
node.val = value
this.IncFreq(node)
} else {
if this.size >= this.ncap {
//移除，最小频次的最早节点
node := this.freq[this.minFreq].RemoveLast()
delete(this.cache, node.key)
this.size--
}
x := &Node{key: key, val: value, freq: 1}
this.cache[key] = x
if this.freq[1] == nil {
this.freq[1] = CreateDL()
}
this.freq[1].AddFirst(x)
//minFreq重置1
this.minFreq = 1
this.size++
}
}
func (this *LFUCache) IncFreq(node *Node) {
_freq := node.freq
this.freq[_freq].Remove(node)
if this.minFreq == _freq && this.freq[_freq].IsEmpty() {
this.minFreq++
delete(this.freq, _freq)
}
node.freq++
if this.freq[node.freq] == nil {
this.freq[node.freq] = CreateDL()
}
this.freq[node.freq].AddFirst(node)
}
type DoubleList struct {
head, tail *Node
}
type Node struct {
prev, next *Node
key, val, freq int
}
//创建新的双链表节点，这里有默认的前后2个节点，方便快速插入和删除
func CreateDL() *DoubleList {
head, tail := &Node{}, &Node{}
head.next, tail.prev = tail, head
return &DoubleList{
head: head,
tail: tail,
}
}
func (this *DoubleList) AddFirst(node *Node) {
node.next = this.head.next
node.prev = this.head
this.head.next.prev = node
this.head.next = node
}
func (this *DoubleList) Remove(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
node.next = nil
node.prev = nil
}
func (this *DoubleList) RemoveLast() *Node {
if this.IsEmpty() {
return nil
}
last := this.tail.prev
this.Remove(last)
return last
}
func (this *DoubleList) IsEmpty() bool {
return this.head.next == this.tail
}
|