​面试经典150题——LRU 缓存

the sun is setting over the desert with joshua trees

1. 题目描述

image-20240414214508788

2.  题目分析与解析

首先讲解一下LRU

LRU 是“Least Recently Used”的缩写,LRU 算法的基本思想是跟踪最近最少使用的数据,并在缓存已满且需要存储新数据时优先驱逐该数据。

LRU 算法通常的工作原理的简化解释:

  1. 当访问或使用一条数据时,将该数据移动到“最近使用”的列表的前面。

  2. 当缓存已满且需要存储新数据时,算法会查看列表的末尾,以找到最近最少使用的数据。

  3. 然后,最近最少使用的数据将被从缓存中驱逐,以腾出空间存储新数据。

这个过程确保了最近使用的数据保留在缓存中,而较旧、使用频率较低的数据在需要时被驱逐。这有助于通过最大限度地确保最相关的数据随时可用来提高缓存系统的效率。

2.1 思路一

注意题目中提示的 函数 getput 必须以 O(1) 的平均时间复杂度运行 ,根据这个信息可能在提示我们是不是会用hashMap(因为O(1))。但是如果使用hashMap我们怎么跟踪它最近是否被使用呢?这时我们可能也会想到使用一个队列,按照队列先进先出的性质,我们就可以实现在容量不够时移除最近最少使用的那个对象。但是如果使用队列也会面临一个问题,那就是如下图所示的情况:

image-20240414215913722

这时如果我要put进去的value为3,那我就需要把队列更新为如下形式:

image-20240414220056336

那就牵涉到了队列的重新更新,肯定无法实现O(1)的要求。

而此时我们想象一下如果对于一个新用到的元素,那必然要把它更新到这个LRU的链子的头部就像上图 3 放在0号位一样,能够在常数时间内进行这样移动的好像链表就能行。

现在我们假设使用链表,对于前面同样的情况:

image-20240414220420606

换成链表后就是一个个单独的节点,那么移动只需要找到当前需要put的节点,找到它的位置及其前后节点,将当前节点放在链表头部,前后节点进行连接不就可以完成题目的要求。注意一下要想在O(1)的时间复杂度中找到这个节点,还是要借助hash。因此我们就可以提出以下思路:

解题思路:

整体思路——构建环形链表,每次插入新节点时,将尾部节点删除(也就是替换),将新节点插入到头部(也是替换)

image-20240415105317682

  1. 定义一个HashMap存储key和Node

  2. 定义一个虚拟头节点指向环形链表的头部

  3. 构造函数:构建一个capacity长度的双向环形链表

  4. get方法:如果key不存在,返回-1;如果key存在,返回value,并将当前节点移动到头部

  5. put方法:如果key存在,更新value,并将当前节点移动到头部;如果key不存在,将新节点插入到头部并将尾部节点删除

  6. 移动到头部方法:如果当前节点是头部节点,直接返回;如果当前节点是中间节点,将当前节点的前一个节点和后一个节点连接,将当前节点插入到头部

  7. 时间复杂度:get和put方法的时间复杂度都是O(1)

  8. 空间复杂度:O(n)

3. 代码实现

4. 相关复杂度分析

这个LRUCache实现的时间复杂度主要集中在put和get方法上。

时间复杂度分析:

  1. get(int key):

    • 在HashMap中查找key的时间复杂度是O(1)。

    • 如果key存在,调用moveToHead方法,该方法的时间复杂度是O(1)。

    • 因此,get方法的总体时间复杂度是O(1)。

  2. put(int key, int value):

    • 如果key已经存在,需要更新其对应的value,这涉及到HashMap的查找和更新操作,时间复杂度均为O(1)。

    • 如果key不存在,需要将新节点插入到头部并将尾部节点删除,这包括HashMap的插入和删除操作,以及moveToHead方法的调用,总体时间复杂度也是O(1)。

    • 因此,put方法的总体时间复杂度是O(1)。

空间复杂度分析:

LRUCache类中使用了HashMap来存储键和节点的映射关系,其空间复杂度为O(capacity)。另外,还有capacity个节点,每个节点占用的空间也是常数级的。因此,LRUCache的总体空间复杂度为O(capacity)。

综上所述,该LRUCache实现的时间复杂度为O(1),空间复杂度为O(capacity)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/548051.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

农业环境监测设备:促进农业可持续发展

TH-NQ14农业环境监测设备在现代化农业发展中扮演着至关重要的角色。这些设备能够实时监测农田环境参数,为农业生产提供科学依据,促进农业可持续发展。 随着技术的不断进步,农业环境监测设备的功能和性能得到了极大的提升。现代的农业环境监测…

Docker篇(三)— Docker的基本操作

目录 镜像操作镜像名称镜像命令案例1-拉取、查看镜像案例2-保存、导入镜像 镜像操作 镜像名称 首先来看下镜像的名称组成: 镜名称一般分两部分组成:[repository]:[tag]。在没有指定tag时,默认是latest,代表最新版本的镜像 如图…

35. UE5 RPG制作火球术技能

接下来,我们将制作技能了,总算迈进了一大步。首先回顾一下之前是如何实现技能触发的,然后再进入正题。 如果想实现我之前的触发方式的,请看此栏目的31-33篇文章,讲解了实现逻辑,这里总结一下: …

一个实例了解JVM运行原理

下面以一个具体的代码示例,来说明Java代码对象是如何分配的,Java代码又是如何在JVM中运行的。 public class JVMCase {// 常量public final static String MAN_SEX_TYPE "man";// 静态变量public static String WOMAN_SEX_TYPE "woman…

MGRE环境下的OSPF配置

拓扑图 R1配置 [r1]int Tunnel 0/0/0 [r1-Tunnel0/0/0]ip add 192.168.7.1 24 [r1-Tunnel0/0/0]tunnel-protocol gre p2mp [r1-Tunnel0/0/0]source 16.0.0.1 [r1-Tunnel0/0/0]nhrp network-id 100[r1]int t0/0/1 [r1-Tunnel0/0/1]ip add 192.168.8.1 24 [r1-Tunnel0/0/1]tunn…

远程抄表系统与配电能效系统在大学学生公寓的应用/远程抄表计费系统

安科瑞薛瑶瑶18701709087 摘要:该校及全国各大高校学生公寓目前收费模式及现状,远程抄表智能系统的必要性及系统运行状况的对比。 关键词:远程抄表智能系统;必要性;优点 0、前言 该校在远程抄表智能系统使用前学生…

文字转语音TTS在线使用经验

文字转语音TTS在线使用经验 文字转语音TTS在线使用经验 2024-04-15 ,今天测试了一下微软 Azure TTS 的新语音引擎,主要测试了英语和中文。 这次 MicroSoft 一共推出了 9 款包括: 美式英语 - en-US-AvaMultilingualNeural 女性 美式英语 - en…

【Java基础学习】面向对象编程

开始时间: April 10, 2024 结束时间: April 16, 2024 阶段: Done 基础部分 类与对象的关系 类是抽象的,概念的,代表一类事物对象是具体的,实际的,代表一个具体事物(实例)类是对象的模板,对象…

基于Springboot+Vue的Java项目-校园管理系统(附演示视频+源码+LW)

大家好!我是程序员一帆,感谢您阅读本文,欢迎一键三连哦。 💞当前专栏:Java毕业设计 精彩专栏推荐👇🏻👇🏻👇🏻 🎀 Python毕业设计 &am…

mysql,oracle,sql server中的默认事务隔离级别查看

一 、事务 一个事务中的一系列的处理操作要么全部成功,要么全部失败。在数据库操作中,一项事务(Transaction)是由一条或多条操作数据库的SQL语句组成的一个不可分割的工作单元。 事务的处理结果有两种: 1)当…

使用AI动作捕捉制作动画图像——Viggle AI教程

使用AI动作捕捉制作动画图像——Viggle AI教程 在数字媒体时代,动画制作已经成为一种流行的艺术形式。最近,我在网上发现了一个非常有趣的AI动画制作工具——Viggle AI。这个工具不仅简单易用,而且目前还是免费的。在这篇博客中,我…

DHCP小实验

实验要求: 看拓扑有两个网段则我们首先需要对200.1.1.0/26进行子网划分,划分为两个子网,为200.1.1.0/27和200.1.1.32/27 我门就可以一边一个网段了,左边为200.1.1.0/27,右边为200.1.1.32/27 1、配置PC1,2…

腾讯EdgeOne产品测评体验——不仅仅是加速,更是您数字安全的坚实盾牌!

EdgeOne 是什么--- 下一代CDN 腾讯云推出的边缘安全加速平台 EO(Tencent cloud EdgeOne,下文简称为 EdgeOne) 是基于腾讯边缘计算节点提供加速和安全的解决方案。即对标传统的 CDN 网络分发节点,但是其在加速和安全防护的方面有更…

从建表语句带你学习doris_表索引

1、doris建表概述 1.1、doris建表模板 CREATE [EXTERNAL] TABLE [IF NOT EXISTS] [DATABASE.]table_name (column_definition1[,column_deinition2,......][,index_definition1,[,index_definition2,]] ) [ENGINE [olap|mysql|broker|hive]] [key_desc] [COMMENT "tabl…

无人零售行业展望:智能化与便利性引领未来

无人零售行业展望:智能化与便利性引领未来 无人零售,这一依靠智能化技术如人工智能、物联网、和大数据的零售模式,正逐步成为全球零售行业的新趋势。该模式允许消费者在没有店员的情况下自助完成购物,提供了24小时服务&#xff0…

Redis集群机制及一个Redis架构演进实例

Replication(主从复制) Redis的replication机制允许slave从master那里通过网络传输拷贝到完整的数据备份,从而达到主从机制。为了实现主从复制,我们准备三个redis服务,依次命名为master,slave1&#xff0c…

季节更迭 关爱不变 | 鲁南制药四季守护您的健康生活

春天,万物复苏的季节,一切都充满了生机和活力。在春日的阳光下,鲜花盛开,绿叶茂盛,鸟儿欢歌,蝴蝶翩翩起舞。我们的身体也需要特别的关爱和养护,保持健康和活力,更好地迎接每一次季节…

MySQL 实例employee表综合查询

目录 表关系图: 例题: 1.查出至少有一个员工的部门。显示部门编号、部门名称、部门位置、部门人数。 2.列出所有员工的姓名及其直接上级的姓名。 3.列出受雇日期早于直接上级的所有员工的编号、姓名、部门名称。 4.列出部门名称和这些部门的员工信…

正五边形C语言绘制方法

正五边形C语言绘制方法 平面几何大家都学过,基本的概念就是点、线、面,三角形、矩形、圆形和椭圆形,还有就是多边形。学几何时都强调用圆规直尺三角板作图,学到角度就用到量角尺。那时我对五角星,六角星很感兴趣。后来…

【攻防世界】lottery

弱比较代码审计 本题已提供源码,如果没提供,输入/robots.txt,发现/.git function buy($req){require_registered();require_min_money(2);$money $_SESSION[money];//接受用户原有money$numbers $req[numbers];//接受输入的数字$win_num…