推广型网站开发公司,怎么做代理ip网站,业务平台,做废旧金属的网站https://leetcode.cn/problems/lru-cache/description/?envTypestudy-plan-v2envIdtop-100-liked
实现语言#xff1a;go lang
LRU
最近最少未使用#xff0c;是一种淘汰策略#xff0c;当缓存空间不够使用的时候#xff0c;淘汰一个最久没有访问的存储单元。目前…https://leetcode.cn/problems/lru-cache/description/?envTypestudy-plan-v2envIdtop-100-liked
实现语言go lang
LRU
最近最少未使用是一种淘汰策略当缓存空间不够使用的时候淘汰一个最久没有访问的存储单元。目前已知较好表现的替换策略具体原因翻教材。
题目要求编写一个LRU具体类完成指定方法Get(key int) int {} 与 Set(key int, value int) {} 并且需要保证两个方法的时间复杂度都需要在O1
既然是是缓存而且是替换策略我们就先假设放在一个数组里面。 最主要需要考虑替换策略。所以我们假定数组已经满了这时候我需要set一个新的键值对进来我需要替换哪一个 这时候就感觉好像似乎需要针对访问顺序产生优先级顺序。但这个优先级顺序不能用排序解决因为无论哪种排序都不可能在O1完成。 每一次最久没有访问的其实可以认为是一个贪心选择。那么假设每一次访问之后都把访问结点往前放那么到淘汰时候一定是末尾的淘汰。
确定出方法就需要确定数据结构以满足时间复杂度的限制。 显然之前假定的数组不可行。因为按照刚才的思路访问的时候都需要改变一下顺序数组显然不好改变顺序。 但链表可以既好改变顺序同时也好删除复杂度都是O1.
确定了数据结构能够解决顺序与删除问题就剩下最后一个问题查找。 无论是Get还是进行删除之前都需要进行查找而且也需要保证复杂度O1。 显然就只剩下hash了。
所以可以确定下来所用的数据结构为链表与hashtable
省下的就是go语言编码的问题了
go container/list
container/list是直接使用双向链表的没有但链表这个选项直接用就可以。 内部数据结构分为Element与List
Element相当于自己写链表的Node内部含有结点值前后结点的指针。 List是相当于进行封装里面全是一堆方法。 比较有用的就是
直接含有size计数Front/Back方法返回头/尾 Elementmove方法移动结点到首部/尾部/随便结点后面delete方法删除某个节点
具体哪个方法查阅一下文档
https://pkg.go.dev/container/list#pkg-functions
方法不详述直接翻官方文档就好了。 import container/listfunc main() {// 构造一个list对象前面这个list代表list这个packagel : list.New()// 需要用什么值直接调用list.PushBack/PushFront然后把值丢进去就可以了// 不需要自己封装Elementl.PushBack(111)}代码
go语言的一些问题 为什么需要使用Pair 其实是我傻了后面发现可以不用 为什么需要插入时候需要Pair 因为题目设定二次访问是更新值如果不设置成指针go是不让修改数据。 为什么delNode.Value.(*Pair) 要这么写 因为源码Element是Any类型也就是interface{}。由于拿出来需要访问以Pair访问Key Value需要进行显示转换 // 需要实现的特征
// 存取o1
// 维持这个队列o1
// put
// 查看字典是否存在
// 如果存在更新队列参数
// 如果使用队列
import container/listtype LRUCache struct {size intcapacity intcache map[int]*list.Elementlist *list.List
}type Pair struct{Key intValue int
}func Constructor(capacity int) LRUCache {l : LRUCache {size: 0,capacity: capacity,cache: make(map[int]*list.Element),list: list.New(),}return l
}func (this *LRUCache)Get(key int) int{if _, ok : this.cache[key]; !ok {return -1}node : this.cache[key]this.list.MoveToFront(node)return node.Value.(*Pair).Value
}func (this *LRUCache) Put(key int, value int) {if _, ok : this.cache[key]; !ok {node : this.list.PushFront(Pair{key, value})this.cache[key] nodethis.sizeif this.size this.capacity {delNode : this.list.Back()nodeValue : delNode.Value.(*Pair)delete(this.cache, nodeValue.Key)this.list.Remove(delNode)this.size--}} else {node : this.cache[key]node.Value.(*Pair).Value valuethis.list.MoveToFront(node)}
}
