GO题解 | #设计LRU缓存结构#

go解题答案

• 时间复杂度O(1)

• 思路概括：双链表+hashtable

• 思路核心：
  1、双链表存储优先级
  2、hahstable实现节点缓存，以O(1)时间获取

  func LRU( operators [][]int ,  k int ) []int {
    // write code here
    ans:=[]int{}
    //初始化lru
    cache:= constructor(k)
    for _,v :=range operators{
        operator:=v[0]
         if operator==1{
            cache.Put(v[1],v[2])
        }else if operator==2{
             res:=cache.Get(v[1])
             ans= append(ans,res)
        }
    }
  
    return ans
  }
  //lru定义
  type LRUCache struct{
    Cache map[int]*DLinkNode
    Head,Tail *DLinkNode
    Size int
    Capacity int
  }
  // 节点定义
  type DLinkNode struct{
    Key,Val int
    Pre,Next *DLinkNode
  }
  //初始化节点
  func initDLinkNode(key int,val int)*DLinkNode{
    return &DLinkNode{
        Key:key,
        Val:val,
    }
  }
  // 初始化lru
  func constructor(capacity int)LRUCache{
    lru:=LRUCache{
        Cache:map[int]*DLinkNode{},
        Head:initDLinkNode(0,0),
        Tail:initDLinkNode(0,0),
        Capacity:capacity,
    }
    lru.Head.Next=lru.Tail
    lru.Tail.Pre=lru.Head
    return lru
  }
  func (this *LRUCache)Get(key int)int{
    // 检查是否存在
    if _,ok:=this.Cache[key];!ok{
        return -1
    }
    // 更新队列头
    node:=this.Cache[key]
    this.MoveToHead(node)
    return node.Val
  }
  func (this *LRUCache)Put(key int ,val int){
    if _,ok:=this.Cache[key];!ok{
        node:=initDLinkNode(key,val)
        this.Cache[key]=node //设置缓存
        this.AddToHead(node) //插入最头
        this.Size++
        //检查是否超过队列大小
        if this.Size>this.Capacity{
            //删除队列
            r:=this.RemoveTail() 
            delete(this.Cache,r.Key)
            this.Size--
        }
    }else{
        node:=this.Cache[key]
        node.Val=val // 更新数据
        this.MoveToHead(node) //更新队列头
    }    
  }
  // 插入队列头
  func (this *LRUCache)AddToHead(node *DLinkNode){
    // 先处理该插入节点的前后
    node.Pre = this.Head 
    node.Next =this.Head.Next
    //再处理相邻检点的前后
    this.Head.Next.Pre=node
    this.Head.Next=node
  }
  // 更新队列头
  func (this *LRUCache)MoveToHead(node *DLinkNode){
    //注意顺序
    this.RemoveNode(node)
    this.AddToHead(node)
  }
  func (this *LRUCache)RemoveNode(node *DLinkNode){
   //顺序无所谓
   node.Pre.Next=node.Next
   node.Next.Pre=node.Pre
  }
  // 移除队尾
  func (this *LRUCache)RemoveTail()*DLinkNode{
    node := this.Tail.Pre // 找到要移除的元素
    this.RemoveNode(node)
    return node
  }

  如果有帮助请点个赞哦， 更多文章请看我的博客

  题主背景

• 从业8年——超级内卷500Q技术经理——目前专注go和微服务架构