【golang必备算法】 Letecode 146. LRU 缓存机制
2021/11/25 1:09:58
本文主要是介绍【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) } }
参考:
https://leetcode-cn.com/problems/lru-cache/solution/jian-dan-shi-li-xiang-xi-jiang-jie-lru-s-exsd/
这篇关于【golang必备算法】 Letecode 146. LRU 缓存机制的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-15SendGrid 的 Go 客户端库怎么实现同时向多个邮箱发送邮件?-icode9专业技术文章分享
- 2024-11-15SendGrid 的 Go 客户端库怎么设置header 和 标签tag 呢?-icode9专业技术文章分享
- 2024-11-12Cargo deny安装指路
- 2024-11-02MongoDB项目实战:从入门到初级应用
- 2024-11-01随时随地一键转录,Google Cloud 新模型 Chirp 2 让语音识别更上一层楼
- 2024-10-25Google Cloud动手实验详解:如何在Cloud Run上开发无服务器应用
- 2024-10-24AI ?先驱齐聚 BAAI 2024,发布大规模语言、多模态、具身、生物计算以及 FlagOpen 2.0 等 AI 模型创新成果。
- 2024-10-20goland工具下,如修改一个项目的标准库SDK的版本-icode9专业技术文章分享
- 2024-10-17Go学习:初学者的简单教程
- 2024-10-17Go学习:新手入门完全指南