《程序员面试金典(第6版)》面试题 16.25. LRU 缓存(自定义双向链表,list库函数,哈希映射)
题目描述
设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。
题目传送门:面试题 16.25. LRU 缓存
-
它应该支持以下操作: 获取数据 get 和 写入数据 put 。
-
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
-
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
解题思路与代码
-
这道题我觉得还是有点迷惑性的,假如说不了解什么是LRU缓存,可能会被“删除最近最少使用”这句话给蒙蔽了双眼,而给出了错误的答案。
-
你可能以为,我需要删除的是访问次数相同的,最近的那个内存,其实不是的。
-
LRU的原理是,如果数据最近被访问过,那么将来被访问的几率也更高。因此,我们在缓存满的时候,会淘汰最长时间未被访问的数据。 -
所以说,做这道题的时候,被误导了一下有点难受的。不过知道了原理,其实这道题也没有那么的困难。这道题的核心是
删除最长时间未被访问过的内存,也就是说,想办法解决了这个问题,这道题也就迎刃而解了。 -
我们可以考虑用
双向链表 + unordered_map去解决这个问题,我们每次添加元素,都从头开始添加。内存满了,删除元素都从队列尾部删除,是不是完美的符合了删除最长时间不访问这个元素的需求。 -
最后,我们访问一个链表内的元素,我们就把这个元素,先从链表中删除,把它从新添加到链表头部,是不是也完美符合题意?
-
那unordered_map的作用是什么呢?它的作用就是让你快速知道你的这查找的这个元素是否在链表内,它的查找复杂度是O(1)的。
-
而双向链表的添加和删除节点的操作本身的时间复杂度也是O(1)的。所以用这两种数据结构,可以完美的去均摊这个时间复杂度。
那又因为面试官考你这道题,肯定是想要考你自定义双向链表的,而不是想看你用库函数。所以我们要自己掌握,如何创建并使用一个自定义的双向链表。
其次,这就意味着库函数的双向链表不重要了吗?恰恰相反,它也十分重要,真正的工作中,肯定也是不可能让你自己创建链表的。所以,矛盾又不矛盾。
那接下来,就看我给大家展现这两种解法的代码都是如何写的吧~
方案一:自定义双向链表 + unordered_map
- 在这道题当中,我们需要实现两个函数,
get 和 put。 - get函数就是查找缓存中对应key的value。put函数就是把元素放到容器内,如果容器满了,就挑一个删除了,再添加。
- 根据题意,当容器满了时,
我们要删除的元素是,最长时间未被使用的元素,这里我们使用的容器是双向链表,我们每次都从链表的头部开始添加元素,如果容器满了,需要删除的元素就一定是容器尾部的元素。 - 再者,我们如果查询了这个元素,而这个元素又在容器内的话,我们就要把它重新移动到头部,那如何移动呢?自然是删除后再添加啦,从当前位置删除,从链表头部添加。
- 这个自定义双向链表,我设置两个哨兵节点,分别是
head与tail,这会使等会的链表操作变得非常的简单。具体的双向链表的其他实现,就请大家来看看代码啦~
具体的代码如下:
class LRUCache {
public:struct Node{int key;int val;Node * prev;Node * next;Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr){};};LRUCache(int capacity) : cap(capacity), size(0), head(new Node(-1,-1)), tail(new Node(-1,-1)) {head->next = tail;tail->prev = head;}int get(int key) {if(map.find(key) == map.end()) return -1;moveNode(map[key]);return map[key]->val;}void put(int key, int value) {if(map.find(key) != map.end()){map[key]->val = value;moveNode(map[key]);}else{if(size == cap){map.erase(tail->prev->key);removeFromList(tail->prev);--size;}Node * node = new Node(key,value);addToHead(node);map[key] = node;++size;}}
private:int cap;int size;Node * head;Node * tail;unordered_map<int,Node*> map;void addToHead(Node * node){node->next = head->next;node->prev = head;head->next->prev = node;head->next = node;}void removeFromList(Node * node){node->next->prev = node->prev;node->prev->next = node->next;}void moveNode(Node * node){removeFromList(node);addToHead(node);}
};

复杂度分析:
这个 LRU 缓存的实现,无论是 get 还是 put 操作,都可以在常数时间内完成,因此时间复杂度是 O(1)。
-
这是因为,我们通过哈希表实现了对任意键值的快速查询,查询的时间复杂度是 O(1)。
- 对于哈希表中存储的每个键值对,我们都有一个对应的链表节点。当需要将某个键值对提到最近使用的位置时,我们可以直接通过哈希表找到对应的链表节点,然后在 O(1) 时间内将其移动到链表的头部。同样,当缓存容量已满,需要淘汰最久未使用的键值对时,我们也可以在 O(1) 时间内从链表尾部删除一个节点。
-
对于空间复杂度,因为哈希表和链表都存储了整个数据,所以空间复杂度是 O(capacity),其中 capacity 是缓存的最大容量。
方案二:使用list + unordered_map
- 这种做法,最大的好处就是带你重新复习了一遍list容器中,各种函数的操作。如果你对list函数的操作不太熟悉的话,你可以看下我写的这篇文章:全面理解:C++中list(双向链表)容器的基础概念与函数解析
其他没什么了,代码的逻辑和上一种一模一样。
具体的代码如下:
class LRUCache {
public:LRUCache(int capacity) : cap(capacity) {}int get(int key) {if(map.find(key) == map.end()) return -1;cache.splice(cache.begin(),cache,map[key]);return map[key]->second;}void put(int key, int value) {if(map.find(key) != map.end()){cache.splice(cache.begin(),cache,map[key]);map[key]->second = value;}else{if(cache.size() == cap){map.erase(cache.back().first);cache.pop_back(); }cache.push_front({key,value});map[key] = cache.begin();}}
private:int cap;list<pair<int,int>> cache;unordered_map<int,list<pair<int,int>>::iterator> map;
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/
复杂度分析:
时间复杂度:
- get 方法:O(1)。unordered_map 用哈希实现,所以查找的平均时间复杂度是O(1),list::splice方法的时间复杂度也是O(1)。
- put 方法:O(1)。unordered_map的插入和删除操作的平均时间复杂度都是O(1),list::push_front和list::pop_back也都是O(1)。
空间复杂度:
- O(capacity)。list和unordered_map都存储了缓存中的所有元素,所以空间复杂度与缓存的容量成正比。
这就是为什么我们使用 list 和 unordered_map 结构来实现 LRU 缓存的原因,它们可以确保所有操作都在常数时间复杂度内完成,而且空间复杂度与缓存的容量成正比。
总结
这道题主要是为了测试你对LRU(Least Recently Used)缓存淘汰策略的理解和实现能力,同时也在考察你的数据结构设计能力。
-
LRU缓存淘汰策略在实际中广泛应用,例如在数据库缓存、浏览器缓存等场景中,都会有其身影。其核心思想是“如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小”。因此,这种算法可以用于预测哪些数据应该被替换出去,从而使缓存的命中率最大。
-
实现这个策略需要用到的数据结构包括哈希表(HashMap)和双向链表(Doubly LinkedList)。其中,哈希表提供了快速查找,而双向链表则可以用来调整数据的优先级。
通过这道题,你可以锻炼并展示出你对以上各种技术和数据结构的掌握程度。同时,这也是一种非常实用的技能,可以直接应用于你未来的项目和工作中。
最后的最后,如果你觉得我的这篇文章写的不错的话,请给我一个赞与收藏,关注我,我会继续给大家带来更多更优质的干货内容。
相关文章:
《程序员面试金典(第6版)》面试题 16.25. LRU 缓存(自定义双向链表,list库函数,哈希映射)
题目描述 设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。 题目传送门:…...
kong网关启用jwt认证插件
认证流程: 1、创建一个用户 2、生成jwt的所需要的key和密钥 3、在https://jwt.io/的生成jwt token 4、启用jwt插件 5、发送请求的时候携带jwt的token信息 官方指导:https://docs.konghq.com/hub/kong-inc/jwt/configuration/examples/ 一、创建一个新的…...
day12 - 图像修复
在图像处理的过程中,经常会遇到图像存在多余的线条或者噪声的情况,对于这种情况我们会先对图像进行预处理,去除掉对图形内容有影响的噪声,在进行后续的处理。 本节实验我们介绍使用图像膨胀来处理图形的多余线条,进行…...
1720_Linux学习中的问题处理
全部学习汇总:GreyZhang/little_bits_of_linux: My notes on the trip of learning linux. (github.com) 这个有点学习的方法论的意思,画个滋味导图顺便整理一下。 遇到问题的时候,解决的方法大致有3中,而针对学习的建议有一部分是…...
七人拼团系统开发模式详解
七人拼团是最近兴起的一个模式,它通过更人性化的奖励机制,将产品利润最大化让利给参与拼团的用户,达到促进用户主动积极裂变和团队平台引流提升销量的效果,下面就来详细说一下这个模式。 七人拼团最大的特点,就是结合了…...
CPU性能优化:分支预测
条件跳转引起的控制冒险虽然也可以通过在流水线中插入空泡来避免,但是当流水线很深时,需要插入更多的空泡。一个20级的流水线为例,如果一条指令需要上一条指令的执行结束才能执行,则需要在这两条指令之间插入19个空泡,…...
过滤器Filter,拦截器Interceptor
过滤器Filter 快速入门 详情 登录校验-Filter package com.itheima.filter;import com.alibaba.fastjson.JSONObject; import com.itheima.pojo.Result; import com.itheima.utils.JwtUtils; import lombok.extern.slf4j.Slf4j; import org.springframework.util.StringUtils…...
kafka整理
kafka整理 一、kafka概述 kafka是apache旗下一款开源的顶级的消息队列的系统, 最早是来源于领英, 后期将其贡献给apache, 采用语言是scala.基于zookeeper, 启动kafka集群需要先启动zookeeper集群, 同时在zookeeper记录kafka相关的元数据 kafka本质上就是消息队列的中间件产品…...
为什么有些情况下需要重写equals()和hashCode()方法?
目录 方法作用实战案例 方法作用 equals():判断对象是否相等,比如判断是否能放入Set集合中 情况1:没有重写equals()方法:由于所有类的默认基类都是Object类,所以默认使用Object类的equals()方法,那就是对象…...
14-Vue技术栈之Vue3快速上手
目录 1.Vue3简介2. Vue3带来了什么2.1 性能的提升2.2 源码的升级2.3 拥抱TypeScript2.4 新的特性 1、海贼王,我当定了!——路飞 2、人,最重要的是“心”啊!——山治 3、如果放弃,我将终身遗憾。——路飞 4、人的梦想是…...
JavaScript高级三、深入面向对象
零、文章目录 JavaScript高级三、深入面向对象 1、编程思想 (1)面向过程介绍 面向过程:分析出解决问题所需要的步骤,然后用函数把这些步骤一步一步实现,使用的时候再一个一个的依次调用就可以了。 (2&…...
static
1. 静态局部变量 : 用于函数体的内部修饰变量,这种变量的生存期长于该函数。 2. 静态全局变量: 定义在函数体外,用于修饰全局变量,表示该变量只在本文件可见。 3. 静态函数: 准确的说,静态函数跟…...
zabbix动作执行失败 No media defined for user.
问题 zabbix动作执行失败 No media defined for user. 详细问题 解决方案 1(导航栏)用户 → \rightarrow →报警媒介 → \rightarrow →添加 2 选择类型 → \rightarrow →收件人 → \rightarrow →添加 3 更新 解决原因 笔者由于未点击更新钮导…...
JavaScript this 关键字
在JavaScript中,this关键字是一个特殊的关键字,它在函数内部使用,用于引用当前执行上下文中的对象。 this的值是在函数调用时动态确定的,它取决于函数的调用方式。下面列举了几种常见的调用方式和this的取值: 1. 全局…...
ubuntu基本信息查询
查询CPU信息 cat /proc/cpuinfo cat /proc/stat top lscpu 查询内存 free -m Options: -b, --bytes show output in bytes -k, --kilo show output in kilobytes -m, --mega show output in megabytes -g, --giga show output in gigab…...
Revit问题:创建牛腿柱和快速生成圈梁
一、Revit中如何用体量创建牛腿柱 牛腿:悬臂体系的挂梁与悬臂间必然出现搁置构造,通常就将悬臂端和挂梁端的局部构造,又称梁托。牛腿的作用是衔接悬臂梁与挂梁, 并传递来自挂梁的荷载。牛腿柱可以用于桥梁、厂房的搭建,…...
k8s节点删除
1.设置该节点为不可调度状态 kubectl cordon k8s-node01 2.驱逐该节点上的pod kubectl drain k8s-node01 --ignore-daemonsets --delete-local-data 若是有pod删除不掉则加上--force参数强制驱逐 3.从集群中删除该node节点 kubectl delete node k8s-node01 4.在k8s-node…...
45°装备系统
45装备系统,规则:1、45 脚后剧情,场景地面出现,个体视角,非群体。2、产生寒暖对立,衣饰自动改变。3、地图下方块蛇,脚步顺逆差,让衣饰自动改变后出现形态特效。(形成进入…...
逻辑漏洞学习-身份验证漏洞
逻辑漏洞就是程序在实现业务逻辑上存在的错误,辑漏洞的出现通常是因为程序在设计业务逻辑时考虑不够全面,或者程序员的思维过程存在瑕疵,没有充分考虑到各种可能的情况 大部分程序员在设计的时候,目标是实现功能需求,…...
【ChatGPT】ChatGPT自动生成思维导图
参考视频:https://edu.csdn.net/learn/38346/613917 应用场景:自学,“研一学生如何学习机器学习”的思维导图 问:写一个“研一学生如何学习机器学习”的思维导图内容,以markdown代码块格式输出 # 研一学生如何学习…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
