【算法】leetcode热题100 146.LRU缓存. container/list用法

https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-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是相当于进行封装，里面全是一堆方法。
比较有用的就是

1. 直接含有size计数
2. Front/Back方法，返回头/尾 Element
3. move方法，移动结点到首部/尾部/随便结点后面
4. delete方法，删除某个节点

具体哪个方法，查阅一下文档

https://pkg.go.dev/container/list#pkg-functions

方法不详述，直接翻官方文档就好了。

import "container/list"func main() {// 构造一个list对象，前面这个list代表list这个packagel := list.New()// 需要用什么值，直接调用list.PushBack/PushFront，然后把值丢进去就可以了// 不需要自己封装Elementl.PushBack(111)}

代码

go语言的一些问题：

1. 为什么需要使用Pair
   其实是我傻了，后面发现可以不用

2. 为什么需要插入时候，需要&Pair
   因为题目设定二次访问是更新值，如果不设置成指针，go是不让修改数据。

3. 为什么delNode.Value.(*Pair) 要这么写
   因为源码Element是Any类型，也就是interface{}。由于拿出来需要访问以Pair访问Key Value，需要进行显示转换

// 需要实现的特征
// 存取o1
// 维持这个队列o1
// put：
// 查看字典是否存在
// 如果存在，更新队列参数
// 如果使用队列？
import "container/list"type 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.size++if 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)}
}