多域名网站,常平东站是东莞东站吗,北京企业网站模板建站开发,企业邮箱认证LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否…LRU 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例
输入
[LRUCache, put, put, get, put, get, put, get, get, get]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4题解
常做常新的一道题其实有点偏向于模板题目了没有做过上来直接写会很抓瞎有一些常见的问题
为什么用双向链表而不是单向链表 将某个节点移动到链表头部或者将链表尾部节点删去都要用到删除链表中某个节点这个操作。你想要删除链表中的某个节点需要找到该节点的前驱节点和后继节点。对于寻找后继节点单向链表和双向链表都能通过 next 指针在O(1)时间内完成对于寻找前驱节点单向链表需要从头开始找也就是要O(n)时间双向链表可以通过前向指针直接找到需要O(1)时间。综上要想在O(1)时间内完成该操作当然需要双向链表实际上就是用双向链表空间换时间了。为什么链表节点需要同时存储 key 和 value而不是仅仅只存储 value 因为删去最近最少使用的键值对时要删除链表的尾节点如果节点中没有存储 key那么怎么知道是哪个 key 被删除进而在 map 中删去该 key 对应的 key-value 呢
一定要多做几遍
type LRUCache struct {size, capacity intcache map[int]*Nodehead, tail *Node
}type Node struct {value, key intprev, next *Node
}func Constructor(capacity int) LRUCache {head : Node{}tail : Node{}head.next tailtail.prev headreturn LRUCache{capacity: capacity,cache: make(map[int]*Node),head: head,tail: tail,}
}func (this *LRUCache) Get(key int) int {// 查询关键字 key 存在于缓存中返回关键字的值不存在则返回 -1if node, exist : this.cache[key]; exist {this.moveToHead(node)return node.value}return -1
}func (this *LRUCache) Put(key int, value int) {// 如果关键字 key 已经存在则变更其数据值 value // 如果不存在则向缓存中插入该组 key-value 。// 如果插入操作导致关键字数量超过 capacity 则逐出最久未使用的关键字if node, exist : this.cache[key]; exist {node.value valuethis.moveToHead(node)} else {newNode : Node{key: key, value: value}this.cache[key] newNodethis.addToHead(newNode)this.sizeif this.size this.capacity {tail : this.removeTail()delete(this.cache, tail.key)this.size--}}
}// Put 操作元素如果不存在向缓存中添加
func (this *LRUCache) addToHead(node *Node) {node.prev this.headnode.next this.head.nextthis.head.next.prev nodethis.head.next node
}// 本来在队列中的元素最近访问Get, Put后移动到队首
func (this *LRUCache) moveToHead(node *Node) {this.removeNode(node)this.addToHead(node)
}// Put 操作插入超出容量则移除节点
func (this *LRUCache) removeNode(node *Node) {node.prev.next node.nextnode.next.prev node.prev
}// 移除最近最久未使用的节点
func (this *LRUCache) removeTail() *Node {node : this.tail.prevthis.removeNode(node)return node
}/*** Your LRUCache object will be instantiated and called as such:* obj : Constructor(capacity);* param_1 : obj.Get(key);* obj.Put(key,value);*/
