-
Notifications
You must be signed in to change notification settings - Fork 0
/
LeetCode146.go
86 lines (80 loc) · 1.59 KB
/
LeetCode146.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
package main
type doublyLinkedNode struct{
prev, next *doublyLinkedNode
key, val int
}
type LRUCache struct {
len, cap int
first, last *doublyLinkedNode
m map[int]*doublyLinkedNode
}
func Constructor(capacity int) LRUCache {
return LRUCache{
cap : capacity,
m : make(map[int]*doublyLinkedNode, capacity),
}
}
func (c *LRUCache) Get(key int) int {
// 存在则返回
if node, ok := c.m[key]; ok{
c.moveToFirst(node)
return node.val
}
return -1
}
func (c *LRUCache) Put(key int, value int) {
node, ok := c.m[key]
if ok {// 更新
node.val = value
c.moveToFirst(node) //如果不放到前面,那么后面的操作可能会将它错误淘汰
}else{
// 插入 淘汰旧数据
if c.len==c.cap{
delete(c.m, c.last.key)
c.removeLast()
}else{
c.len++
}
node = &doublyLinkedNode{
key: key,
val: value,
}
c.m[key] = node
c.insertToFirst(node)
}
}
func (c *LRUCache)removeLast(){
// 删除末尾节点:更新倒数第二个节点指针
if c.last.prev!= nil{// 非空链表
c.last.prev.next = nil
}else{
c.first = nil
}
c.last = c.last.prev
}
func (c *LRUCache)moveToFirst(node *doublyLinkedNode){
// 先删除再插入
switch node{
case c.first:
return
case c.last:
c.removeLast()
default:
// 删除节点:更新前后节点指针
node.prev.next = node.next
node.next.prev = node.prev
}
c.insertToFirst(node)
}
func (c *LRUCache)insertToFirst(node *doublyLinkedNode){
// 异常(空链表)
if c.last==nil{
c.last = node
}else{
// 双向指针
node.next = c.first
c.first.prev = node
}
// 指定头节点
c.first = node
}