面试某家公司居然让我写LRU，写了40分钟才写出来orz我好菜。然后交给面试官的版本有bug。 面试后去leetcode提交又debug了下，可以通过了。 leetcode地址：https://leetcode.cn/problems/lru-cache/
我封装了一个链表，所以写LRU的时候就比较简洁。
func (this *LRUCache) Get(key int) int {
if v, ok := this.m[key]; ok {
this.linkedList.Remove(this.m[key])
this.linkedList.PutOnHead(this.m[key])
return v.val
} else {
return -1
}
}
func (this *LRUCache) Put(key int, value int) {
if v, ok := this.m[key]; ok {
v.val = value
this.linkedList.Remove(this.m[key])
this.linkedList.PutOnHead(this.m[key])
} else {
this.m[key] = &Node{key: key, val: value}
this.linkedList.PutOnHead(this.m[key])
this.len++
if this.len > this.capacity {
delete(this.m, this.linkedList.GetTail().key)
this.linkedList.Pop()
this.len--
}
}
}
但是对于链表要注意的事项：
- remove的时候要如果remove的是tail的话，记得更新tail
- remove的时候如果要remove的是head的话，需要更新head为head.next。
- 并且如果更新head之后是nil，那l.head.prev = nil是不需要的。这个主要是应对capacity=1的特例。
type LRUCache struct {
m map[int]*Node
capacity int
len int
linkedList *LinkedList
}
type Node struct {
key int
val int
prev *Node
next *Node
}
type LinkedList struct {
head *Node
tail *Node
}
func NewLinkedList() *LinkedList {
t := &LinkedList{}
return t
}
func (l *LinkedList) GetHead() *Node {
return l.head
}
func (l *LinkedList) GetTail() *Node {
return l.tail
}
func (l *LinkedList) Pop() {
if l.tail == nil {
return
}
l.tail = l.tail.prev
l.tail.next = nil
}
func (l *LinkedList) PutOnHead(node *Node) {
if l.head == nil {
l.head = node
l.tail = node
l.head.next = nil
l.head.prev = nil
return
}
node.next = l.head
l.head.prev = node
l.head = node
node.prev = nil
}
func (l *LinkedList) Remove(node *Node) {
if node == l.head {
l.head = l.head.next
if l.head != nil {
l.head.prev = nil
}
return
}
if node == l.tail {
l.tail = l.tail.prev
l.tail.next = nil
return
}
if node.prev != nil {
node.prev.next = node.next
}
if node.next != nil {
node.next.prev = node.prev
}
}
func Constructor(capacity int) LRUCache {
t := LRUCache{
m: make(map[int]*Node),
capacity: capacity,
linkedList: NewLinkedList(),
}
return t
}
func (this *LRUCache) Get(key int) int {
if v, ok := this.m[key]; ok {
this.linkedList.Remove(this.m[key])
this.linkedList.PutOnHead(this.m[key])
return v.val
} else {
return -1
}
}
func (this *LRUCache) Put(key int, value int) {
if v, ok := this.m[key]; ok {
v.val = value
this.linkedList.Remove(this.m[key])
this.linkedList.PutOnHead(this.m[key])
} else {
this.m[key] = &Node{key: key, val: value}
this.linkedList.PutOnHead(this.m[key])
this.len++
if this.len > this.capacity {
delete(this.m, this.linkedList.GetTail().key)
this.linkedList.Pop()
this.len--
}
}
}