首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数：144640 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，操作次数是 n ，并有如下两个功能
1. set(key, value)：将记录(key, value)插入该结构
2. get(key)：返回key对应的value值

提示:
1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过k时，移除最不经常使用的记录。
3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value
若opt=1，接下来两个整数key, value，表示set(key, value)
若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
对于每个opt=2，输出一个答案
4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为
数据范围： ，
示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出

[1,-1]

说明

[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
示例2

输入

[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2

输出

[1,-1,-1,3,4]
算法知识视频讲解
开通博客
头像 SkyRunner
发表于 2020-08-31 16:45:01
import java.util.*; public class Solution { private Map<Integer, Node> map = new HashMap<>(); private Node head = new Node(-1,-1) 展开全文
去ta的博客 赞 (114) 回复(15) 收起
头像 我也改个名
发表于 2020-09-05 09:05:02
看题解太少了，小白也贴一个c++版本的。思路借鉴的@Kid201805122110924博主分享的题解思路。开始初始化一个head节点与一个tail节点，方便以后插入节点和删除节点，中间放置操作的节点。 [1,1,1] 当我们遇到第一个set方法的时候 就需要插入到head 和tail 之间， 展开全文
去ta的博客 赞 (83) 回复(4) 收起
头像 wyg_031113
发表于 2020-10-21 23:16:06
set 和 get的时候要先看在不在hash表中，在的话，从list和hash表中移除，再重新添加进list头部和hash表。另外添加元素的时候要注意超过容量就从list尾部淘汰元素，并删除hash表中对应的元素。stl list的iterator是可以保存的，List添加删除元素不会导致其他ite 展开全文
去ta的博客 赞 (49) 回复(10) 收起
头像 一只弱小的Kid
发表于 2020-09-04 09:18:53
写在前面 本题是看着大佬的代码写的，讲讲大佬的思路https://www.nowcoder.com/profile/797566439 解法 样例 [[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3第一个数字 1 代表 set方法， 2 代表 get方法第 展开全文
去ta的博客 赞 (26) 回复(7) 收起
头像 宫水三叶的刷题日记
发表于 2021-07-03 14:53:38
基本分析 LRU 是一种十分常见的页面置换算法。 将 LRU 翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），选择最久未被使用的数据进行淘汰。 题目让我们实现一个容量固定的 LRUCache 。如果插入数据时，发现容器已满时，则先按照 LRU 规则淘汰一个数据，再将新数据插入，其中「插入 展开全文
去ta的博客 赞 (26) 回复(4) 收起
头像 麻豆出品
发表于 2020-09-06 10:37:34
这题文字有点多呀，实际上是让你设计数据结构：⾸先要接收⼀个 capacity 参数作为 缓存的最⼤容量，然后实现两个 API，⼀个是 put(key, val) ⽅法存⼊键值 对，另⼀个是 get(key) ⽅法获取 key 对应的 val，如果 key 不存在则返回 -1。要让 put 和 get 展开全文
去ta的博客 赞 (18) 回复(8) 收起
头像 hongjunxin
发表于 2020-12-11 10:58:47
解题思路 键值对的查询，首选 map。又因为本题中 map 只是用来查询，不涉及排序，所以采用 unordered_map 维护最近使用的元素，这涉及了出队和入队的概念，但因为 queue 只能操作头部和尾部的元素，所以不适用于本题。而 list 既满足了对头/尾元素的操作，也可以对中间元素进行删 展开全文
去ta的博客 赞 (15) 回复(3) 收起
头像 ronincccc
发表于 2020-09-16 22:33:14
#include <unordered_map> #include <iterator> class Solution { public: vector<int> LRU(vector<vector<int> >& op 展开全文
去ta的博客 赞 (13) 回复(2) 收起
头像 王清楚
发表于 2021-06-04 18:23:08
首先，我们先来看一下LRU缓存结构是什么LRU是Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。 有两操作：set(key,value) 插入操作,缓存区有限定的大小，如果已满的话，需要将最近最久未使用的页面淘汰以后再插入。 展开全文
去ta的博客 赞 (12) 回复(1) 收起
头像 LaN666
发表于 2020-11-30 20:35:41
import java.util.*; public class Solution {     /**      * lru design &nb 展开全文
去ta的博客 赞 (12) 回复(1) 收起

问题信息

模拟
难度：
398条回答 15228浏览

热门推荐

通过挑战的用户

相关试题

设计LRU缓存结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号