【golang必備算法】 Letecode 146. LRU 緩存機制
力扣鏈接:146. LRU 緩存機制
思路:哈希表 + 雙向鏈表
為什麼必須要用雙向鏈表?
因為我們需要刪除操作。刪除一個節點不光要得到該節點本身的指針,也需要操作其前驅節點的指針,而雙向鏈表才能支持直接查找前驅,保證操作的時間複雜度 O(1)。
為什麼要在鏈表中同時存儲 key 和 val,而不是只存儲 val?
當緩存容量已滿,我們不僅僅要刪除最後一個節點,還要把哈希表 中映射到該節點的 key 同時刪除,而這個 key 只能由 節點得到。如果 節點結構中只存儲 val,那麼我們就無法得知 key 是什麼,就無法刪除 哈希表中的鍵,造成錯誤。
代碼
我這裡是向尾部添加數據,所以頭部的是不活躍的數據值
type LRUCache struct { //LRU 緩存結構
capacity int // 容量
m map[int]*Node //哈希表
cache *NodeList //雙向鏈表
}
type Node struct{ //節點結構
key int
value int
prev *Node //前一個節點
next *Node //後一個節點
}
func initNode(key,value int)*Node{ //初始化節點
return &Node{
key:key,
value:value,
}
}
type NodeList struct{ //鏈表結構
head *Node //鏈表頭節點
last *Node //鏈表尾節點
size int //元素個數
}
func initList ()*NodeList{ //初始化鏈表
dil:=&NodeList{
head:initNode(0,0),
last:initNode(0,0),
size:0,
}
dil.head.next=dil.last
dil.last.prev=dil.head
return dil
}
func (this *NodeList)addNodeinlist(node *Node){ //向鏈表中插入節點,向鏈表尾部插節點
node.prev=this.last.prev
this.last.prev=node
node.prev.next=node
node.next=this.last
this.size++
}
func (this *NodeList)deleteNodeinlist (node *Node){ //刪除鏈表中的某一結點
node.prev.next=node.next
node.next.prev=node.prev
node.next=nil
node.prev=nil
this.size--
}
func (this *NodeList)delfirstNode()*Node{ //刪除第一個節點,並且返回
if this.head.next==this.last{
return nil
}
t:=this.head.next
this.deleteNodeinlist(t)
return t
}
func Constructor(capacity int) LRUCache { //初始化 LRU 緩存
return LRUCache{
capacity:capacity,
m:make(map[int]*Node,0),
cache:initList(),
}
}
func (this *LRUCache)addkey(key,value int){ //添加元素
node:=initNode(key,value)
//增加map映射
this.m[key]=node
//在鏈表中添加元素
this.cache.addNodeinlist(node)
}
func (this *LRUCache)makekey(key int){ // 將某個 key 調整為最近使用的元素
//找到節點
node:=this.m[key]
//刪除節點
this.cache.deleteNodeinlist(node)
// 添加到鏈表尾部
this.cache.addNodeinlist(node)
}
func (this *LRUCache)deletekey(key int){ //刪除元素
//刪除鏈表中節點
this.cache.deleteNodeinlist(this.m[key])
//刪除map映射
delete(this.m,key)
}
func (this *LRUCache)deletefirkey(){ //刪除最久未使用的元素
// 鏈表的第一個就是最近最少使用的元素
node:=this.cache.delfirstNode()
// 刪除映射
delete(this.m,node.key)
}
func (this *LRUCache) Get(key int) int {
if _,ok:=this.m[key];ok{
//存在
this.makekey(key) //將某個 key 調整為最近使用的元素
return this.m[key].value
}else{
//不存在
return -1
}
}
func (this *LRUCache) Put(key int, value int) {
// 檢查key存不存在
if _,ok:=this.m[key];ok{
//存在
//刪除元素
this.deletekey(key)
//添加元素到尾部
this.addkey(key,value)
}else{
//不存在
if this.capacity==this.cache.size{
//緩存達到上限
//刪除最久未使用的元素
this.deletefirkey()
}
//添加元素到尾部
this.addkey(key,value)
}
}
參考:
//leetcode-cn.com/problems/lru-cache/solution/jian-dan-shi-li-xiang-xi-jiang-jie-lru-s-exsd/