【golang必備算法】 Letecode 146. LRU 緩存機制

力扣鏈接:146. LRU 緩存機制

image-20211124214033754

思路:哈希表 + 雙向鏈表

img

為什麼必須要用雙向鏈表?

因為我們需要刪除操作。刪除一個節點不光要得到該節點本身的指針,也需要操作其前驅節點的指針,而雙向鏈表才能支持直接查找前驅,保證操作的時間複雜度 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/