首页 > 试题广场 >

LFU缓存结构设计

[编程题]LFU缓存结构设计

一个缓存结构需要实现如下功能。

但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；

如果调用次数最少的key有多个，上次调用发生最早的key被删除

这就是LFU缓存替换算法。实现这个结构，K作为参数给出

[要求]

set和get方法的时间复杂度为O(1)

第一行两个个整数N, K，表示操作数量以及缓存结构大小
接下来N行，第一行一个整数opt表示操作类型。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1

对于每个操作2，输出一个答案

示例1

输入

4
-1

在执行"1 2 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

算法知识视频讲解

暂无题解

哈希

上传者：小小

难度：

4条回答 9收藏 3059浏览

查看代码

LFU缓存结构设计

扫一扫，把题目装进口袋