外贸网,番禺网站 优化,做网站 图片显示不出来,网络服务费的资金产出有哪些力扣第146题#xff1a;LRU缓存 一、LRU算法1. 基本概念2. LRU 和 LFU 的区别#xff1a;3. 为什么 LRU 不需要记录使用频率#xff1f; 二、Golang代码实现三、代码图解1. LRUCache、DLinkedNode两个结构体2. 初始化结构体对象3. addToHead函数4. removeNode函数5. moveToH… 力扣第146题LRU缓存 一、LRU算法1. 基本概念2. LRU 和 LFU 的区别3. 为什么 LRU 不需要记录使用频率 二、Golang代码实现三、代码图解1. LRUCache、DLinkedNode两个结构体2. 初始化结构体对象3. addToHead函数4. removeNode函数5. moveToHead函数6. removeTail函数7. Get函数8. Put函数 一、LRU算法
1. 基本概念
在 LRU 算法中首部节点的含义是最近最常访问的节点而不是使用频率最高的节点。LRULeast Recently Used 是一种基于最近使用时间而非使用频率的缓存淘汰算法核心思想是最近使用的数据应该优先保留最近很久未使用的数据应该被淘汰。
2. LRU 和 LFU 的区别
LRULeast Recently Used基于数据的使用时间最近访问的节点会移动到链表头部而最久未访问的节点会被淘汰。它只关注最后一次访问的时间不记录具体的访问次数。LFULeast Frequently Used基于数据的使用频率频率最高的节点会优先保留频率最低的节点会被淘汰。
3. 为什么 LRU 不需要记录使用频率
在 LRU 算法中只需要维护每个节点的访问顺序而不需要记录节点的访问次数。每次访问某个节点时将该节点移动到链表的头部而最久未使用的节点则自然在链表尾部。所以要获取最近访问的节点直接访问链表的头部节点即可。
二、Golang代码实现
type LRUCache struct {size intcapacity intcache map[int]*DLinkedNodehead, tail *DLinkedNode
}type DLinkedNode struct {key, val intprev, next *DLinkedNode
}func initDLinkedNode(key, val int) *DLinkedNode {return DLinkedNode{key: key,val: val,}
}func Constructor(capacity int) LRUCache {l : LRUCache{cache: map[int]*DLinkedNode{},head: initDLinkedNode(0, 0),tail: initDLinkedNode(0, 0),capacity: capacity,}l.head.next l.taill.tail.prev l.headreturn l
}func (this *LRUCache) addToHead(node *DLinkedNode) {node.prev this.headnode.next this.head.nextthis.head.next.prev nodethis.head.next node
}func (this *LRUCache) removeNode(node *DLinkedNode) {// 将节点从链表中单独抽出来node.prev.next node.nextnode.next.prev node.prev
}func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)this.addToHead(node)
}func (this *LRUCache) removeTail() *DLinkedNode {node : this.tail.prevthis.removeNode(node)delete(this.cache, node.key)return node
}// 通过cache的map关系找到对应的值该值存储在node的val属性中。
func (this *LRUCache) Get(key int) int {// 如果key是不存在的那就返回-1if _, 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 : initDLinkedNode(key, val)this.cache[key] nodethis.addToHead(node)this.sizeif this.size this.capacity {removed : this.removeTail()delete(this.cache, removed.key)this.size--}} else {node : this.cache[key]node.val valthis.moveToHead(node)}
}三、代码图解
1. LRUCache、DLinkedNode两个结构体
type LRUCache struct {size intcapacity intcache map[int]*DLinkedNodehead, tail *DLinkedNode
}type DLinkedNode struct {key, val intprev, next *DLinkedNode
}map理解为一个存储键值对映射的地方来1,1就存储1,1来2,2就存储2,2。
至于这些keyval的顺序就用链表来控制。为了方便插入、删除节点所以采用双向链表。
将map和双向链表结合起来就是将map的val值设置为DoubleNode类型双向链表类型DoubleNode里面设置有keyval两个属性不是映射哦这里的key和map的key是一样大小的值。
最后的效果就是通过map的key找到DoubleNode节点然后找到该节点里面的val属性至于keyval的顺序是由双向链表去排的map就是个映射到节点的地方找到节点就等于找到val。
2. 初始化结构体对象
func initDLinkedNode(key, value int) *DLinkedNode {return DLinkedNode{key: key,value: value,}
}func Constructor(capacity int) LRUCache {l : LRUCache{cache: map[int]*DLinkedNode{},head: initDLinkedNode(0, 0),tail: initDLinkedNode(0, 0),capacity: capacity,}l.head.next l.taill.tail.prev l.headreturn l
}3. addToHead函数
func (this *LRUCache) addToHead(node *DLinkedNode) {node.prev this.headnode.next this.head.nextthis.head.next.prev nodethis.head.next node
}注意这里关于节点的顺序其实是在结构体外去排的这个节点的顺序并不是排在两个结构体内的哦。
4. removeNode函数
// 将节点从链表中单独抽出来
func (this *LRUCache) removeNode(node *DLinkedNode) {node.prev.next node.nextnode.next.prev node.prev
}5. moveToHead函数
func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)this.addToHead(node)
}把node节点从链表中打断抽出来然后将node节点移到this.head后面
6. removeTail函数
func (this *LRUCache) removeTail() *DLinkedNode {node : this.tail.prevthis.removeNode(node)delete(this.cache, node.key)return node
}因为map的key无法直接获得而node.key和map的key一样所以用node.key。
7. Get函数
// 通过cache的map关系找到对应的值该值存储在node的val属性中。
func (this *LRUCache) Get(key int) int {// 如果key是不存在的那就返回-1if _, ok : this.cache[key]; !ok {return -1}node : this.cache[key]this.moveToHead(node)return node.val
}8. Put函数
func (this *LRUCache) Put(key int, val int) {if _, ok : this.cache[key]; !ok {node : initDLinkedNode(key, val)this.cache[key] nodethis.addToHead(node)this.sizeif this.size this.capacity {removed : this.removeTail()delete(this.cache, removed.key)this.size--}} else {node : this.cache[key]node.val valthis.moveToHead(node)}
}!ok是表示如果map里面的key为空那就创建一个相应的新节点让map存储一下key和该节点的映射关系然后将该节点插入到链表头部
如果超过LRUCahce的容量就删除最后一个节点。
如果map里面的key不是空的那就更新一下map存储的节点然后将其移动到头部。
