郑州网站建设开发公司,北京文化馆设计公司怎么看,wordpress邮件 插件,建设通相似网站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);*/
