感覺沒很難，不過還是寫了很久
我好爛
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