国外做的好的电商网站推荐,广告制作公司起名,下列不属于网站开发技术的是,免费问题咨询146. LRU 缓存机制
运用你所掌握的数据结构#xff0c;设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回…146. LRU 缓存机制
运用你所掌握的数据结构设计和实现一个 LRU (最近最少使用) 缓存机制 。 实现 LRUCache 类
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 void put(int key, int value) 如果关键字已经存在则变更其数据值如果关键字不存在则插入该组「关键字-值」。当缓存容量达到上限时它应该在写入新数据之前删除最久未使用的数据值从而为新的数据值留出空间。
进阶你是否可以在 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
解题思路
基于链表和hashmap实现LRU
每次新增key的时候如果key已经存在了就将key移到链表头并且修改value。如果key不存在直接将key插入队头。如果已经超出LRU的大小就删除链表尾部的key每次get的时候如果key存在就将这个key移到链表头并且返回
代码
type LRUCache struct {capacity inthead *Nodetail *Nodecache map[int]*Node
}
type Node struct {pre *Nodenext *Nodekey intval int
}var c LRUCache
func Constructor(capacity int) LRUCache {c.cache map[int]*Node{}c.capacitycapacityc.headNode{val: -1}c.tailNode{val: -1}c.head.nextc.tailc.tail.prec.headreturn c
}func (lru *LRUCache) Get(key int) int {node,ok : c.cache[key]if ok {p,n : node.pre,node.nextp.nextnn.prepth:lru.head.next//插入头节点lru.head.nextnodenode.prelru.headnode.nextthth.prenodereturn node.val}return -1
}func (lru *LRUCache) Put(key int, value int) {if lru.Get(key)!-1 {lru.head.next.valvaluereturn}if lru.capacity0 {delete(lru.cache,lru.tail.pre.key)tl : lru.tail.pre.pretl.nextlru.taillru.tail.pretllru.capacity}node : Node{key: key,val: value,next: lru.head.next,pre: lru.head,}lru.head.next.prenodelru.head.nextnodelru.cache[key]nodelru.capacity--
}/*** Your LRUCache object will be instantiated and called as such:* obj : Constructor(capacity);* param_1 : obj.Get(key);* obj.Put(key,value);*/
