力扣链接：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)

    }

}

参考：

https://leetcode-cn.com/problems/lru-cache/solution/jian-dan-shi-li-xiang-xi-jiang-jie-lru-s-exsd/

巴特西

【golang必备算法】 Letecode 146. LRU 缓存机制

力扣链接：146. LRU 缓存机制

代码

最新文章

热门文章