设计LRU缓存结构_

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

数据范围:

$1\leq capacity<=10^5$
$0\leq key,val \leq 2\times 10^9 \$
$1\leq n\leq 10^5$

说明

我们将缓存看成一个队列，最后一个参数为2代表capacity，所以
Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
output=s.get(1);// 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null" 
output=s.get(2);// 因为get(2)操作，不存在对应的key，故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null" 
output=s.get(1);// 因为get(1)操作，不存在对应的key，故get操作返回"-1"
output=s.get(3);//因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
output=s.get(4);//因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"

class Solution: class DNode: def __init__(self, key: int, val: int): self.before, self.after = self, self self.val = val self.key = key def __init__(self, capacity: int): self.limit = capacity self.dummy = self.DNode(-1, -1) self.idx = {} def get(self, key: int) -> int: if key in self.idx.keys(): tmp = self.remove(key) self.set(key, tmp) return tmp else: return -1 def set(self, key: int, value: int) -> None: tmp = self.DNode(key, value) if key in self.idx.keys(): self.remove(key) else: if len(self.idx) == self.limit: self.remove(self.dummy.before.key) tmp.after = self.dummy.after self.dummy.after = tmp tmp.after.before = tmp tmp.before = self.dummy self.idx[key]=tmp def remove(self, key: int): if key in self.idx: tmp = self.idx[key] tmp.before.after = tmp.after tmp.after.before = tmp.before self.idx.pop(key) return tmp.val

class Solution: def __init__(self, capacity: int): self.capacity = capacity self.buf = dict() # Python 3.6 之后的 dict 默认有序，所以不需要其他数据结构 def get(self, key: int) -> int: ret = self.buf.get(key, -1) if key in self.buf: self.buf.pop(key) self.buf[key] = ret return ret def set(self, key: int, value: int) -> None: if key in self.buf: self.buf.pop(key) elif len(self.buf) >= self.capacity: tmp = next(iter(self.buf.keys())) # 快速获取第一个 key self.buf.pop(tmp) self.buf[key] = value

设计LRU缓存结构

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题