这篇文章主要为大家展示了“leetcode中LRU缓存机制的示例分析”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“leetcode中LRU缓存机制的示例分析”这篇文章吧。
设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
计算
安全
数据库
网络和加速
企业服务
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // 返回 1cache.put(3, 3); // 该操作会使得密钥 2 作废cache.get(2); // 返回 -1 (未找到)cache.put(4, 4); // 该操作会使得密钥 1 作废cache.get(1); // 返回 -1 (未找到)cache.get(3); // 返回 3cache.get(4); // 返回 4解题思路：
1，存储和查找
看到题目要我们实现一个可以存储 key-value 形式数据的数据结构，并且可以记录最近访问的 key 值。首先想到的就是用字典来存储 key-value 结构，这样对于查找操作时间复杂度就是 O(1)O(1)。
但是因为字典本身是无序的，所以我们还需要一个类似于队列的结构来记录访问的先后顺序，这个队列需要支持如下几种操作：
在末尾加入一项
去除最前端一项
将队列中某一项移到末尾
首先考虑列表结构。
2，LRU的实现
利用双向链表实现
双向链表有一个特点就是它的链表是双路的，我们定义好头节点和尾节点，然后利用先进先出（FIFO），最近被放入的数据会最早被获取。其中主要涉及到添加、访问、修改、删除操作。首先是添加，如果是新元素，直接放在链表头上面，其他的元素顺序往下移动；访问的话，在头节点的可以不用管，如果是在中间位置或者尾巴，就要将数据移动到头节点；修改操作也一样，修改原值之后，再将数据移动到头部；删除的话，直接删除，其他元素顺序移动；
type LRUCache struct { capacity int len int hashMap map[int]*Node head *Node tail *Node}type Node struct{ Prev *Node Next *Node Val int Key int}func Constructor(capacity int) LRUCache { m:=make(map[int]*Node) lru:= LRUCache{capacity:capacity,hashMap:m,head:&Node{},tail:&Node{}} lru.head.Next=lru.tail lru.tail.Prev=lru.head return lru}func (this *LRUCache) Get(key int) int { if v,ok:=this.hashMap[key];ok{ v.Prev.Next=v.Next v.Next.Prev=v.Prev n:=this.head.Next this.head.Next=v v.Prev=this.head n.Prev=v v.Next=n return v.Val } return -1}func (this *LRUCache) Put(key int, value int) { if v,ok:=this.hashMap[key];ok{ v.Prev.Next=v.Next v.Next.Prev=v.Prev n:=this.head.Next this.head.Next=v v.Prev=this.head n.Prev=v v.Next=n v.Val=value return } if this.len<this.capacity{ this.len++ node:=&Node{ Val:value, Key:key, } this.hashMap[key]=node n:=this.head.Next this.head.Next=node node.Prev=this.head node.Next=n n.Prev=node }else{ t:=this.tail.Prev this.tail.Prev.Prev.Next=this.tail this.tail.Prev= this.tail.Prev.Prev t.Val=value delete(this.hashMap,t.Key) t.Key=key this.hashMap[key]=t hn:=this.head.Next this.head.Next=t t.Prev=this.head t.Next=hn hn.Prev=t } return}/** * Your LRUCache object will be instantiated and called as such: * obj := Constructor(capacity); * param_1 := obj.Get(key); * obj.Put(key,value); */以上是“leetcode中LRU缓存机制的示例分析”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
