感觉没很难，不过还是写了很久
我好烂
https://imgur.com/iIQ9Orr
146. LRU Cache
请设计一个Data structure 可以实现Least Recently Used cache
要包含Constructor、get、put这三个function
get、put都要在o(1)的时间达成
思路:
用双向link list以及hast table实现
link list的first、last node是空的节点
实际的第一个、最后的node分别是first.next、last.prev
这样可以避免只有一个节点会出现的麻烦
golang code
type node struct {
next *node
prev *node
val int
key int
}
type LRUCache struct {
first *node
last *node
capacity int
table map[int]*node
}
func Constructor(capacity int) LRUCache {
first := &node{val: -1, key: -1}
last := &node{val: -1, key: -1}
return LRUCache{capacity: capacity, table: make(map[int]*node), first: first,
last: last}
}
func (this *LRUCache) Get(key int) int {
if this.table[key] == nil {
return -1
}
if this.last.prev.key == key {//当目前的key==last.prev不用更改
return this.table[key].val
}
node := this.table[key]
node.prev.next, node.next.prev = node.next, node.prev
node.prev, this.last.prev.next = this.last.prev, node
node.next, this.last.prev = this.last, node
return node.val
}
func (this *LRUCache) Put(key int, value int) {
if this.table[key] != nil {
node := this.table[key]
node.val = value
if this.last.prev.key != key {//当目前的key==last.prev不用更改
node.prev.next, node.next.prev = node.next, node.prev
node.prev, this.last.prev.next = this.last.prev, node
node.next, this.last.prev = this.last, node
}
} else {
if this.first.next == nil {
this.first.next = &node{val: value, key: key, prev: this.first, next: this.
last}
this.last.prev = this.first.next
this.table[key] = this.first.next
this.capacity