Re: [閒聊] 每日leetcode
感覺沒很難，不過還是寫了很久
我好爛
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--
return
} else {
if this.capacity == 0 {
this.table[this.first.next.key] = nil
this.first.next = this.first.next.next
this.first.next.prev = this.first
} else {
this.capacity--
}
node := &node{val: value, key: key, prev: this.last.prev, next: this.last}
this.last.prev, this.last.prev.next = node, node
this.table[key] = node
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.166.217 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1709993325.A.603.html
推
03/09 22:09,
1年前
, 1F
03/09 22:09, 1F
推
03/09 22:22,
1年前
, 2F
03/09 22:22, 2F
討論串 (同標題文章)
完整討論串 (本文為第 29 之 1552 篇)：