这篇文章主要为大家展示了“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); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.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缓存机制的示例分析”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
原创文章,作者:bd101bd101,如若转载,请注明出处:https://blog.ytso.com/224007.html