【LeetCode】【算法】146. LRU缓存

LeetCode - 146.LRU缓存

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存
int get(int key)如果关键字key存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value)如果关键字key已经存在,则变更其数据值value;如果不存在,则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity,则应该逐出最久未使用的关键字。
函数get和put必须以 O(1) 的平均时间复杂度运行。

实现思路

LRU本质就是通过一个队列实现的,对于put函数和get函数,最特别的地方在于访问时需要将访问的节点挪到队尾。

  1. 创建ListNode以实现节点。其中包含int key, int value, ListNode next, ListNode prev(双向指针的实现)
  2. 在LRU类中的属性包括:
    I. 虚拟头尾节点ListNode dummyHead, dummyTail;
    II. HashMap用于以O(1)平均复杂度访问到目标节点Map<Integer, ListNode> map;(如果需要遍历整个链表来找目标节点,就不是O(1)的复杂度了)
    III. int capacity表示链表的容量,这是题目需要指定的
    IV. int listLen用于记录当前链表的长度
  3. 初始化LRU类,就是对上面的这些属性做一个初始化,记得虚拟头尾节点的next属性和prev属性需要相连
  4. put方法思路:
    I. 使用map来检查这个节点是否在链表中;
    ① 如果在链表中,则通过map得到这个节点,将该节点从链表中删除,并给改节点赋予新的值;
    ② 如果不在链表中,又分为listLen>=capacitylistLen<capacity的情况(也就是链表容量是否超过指定容量了)
    情况1:链表当前容量已经达到了指定容量,需要删除最久未访问节点(队头),使用虚拟头结点dummyHead来做删除;根据给定的key和value新建一个节点
    情况2:链表当前容量未达到指定容量,则链表长度++,根据给定的key和value新建一个节点
    II. 利用dummyTail将该节点放到链表的最后,并更新map中的内容
  5. get方法思路:
    I. 使用map来检查这个节点是否在链表中,不在返回-1;
    II. 否则利用map来拿到这个节点,将它从链表中移除;并利用dummyTail将该节点放到链表最后,返回该节点的值

实现代码

class LRUCache {class ListNode{int key;int value;ListNode next;ListNode prev;public ListNode() {}public ListNode(int key, int value) {this.key = key;this.value = value;}}ListNode dummyHead;ListNode dummyTail;Map<Integer, ListNode> map;int capacity;int listLen;public LRUCache(int capacity) {map = new HashMap<>();dummyHead = new ListNode();dummyTail = new ListNode();dummyHead.next = dummyTail;dummyTail.prev = dummyHead;this.capacity = capacity;this.listLen = 0;}public void put(int key, int value) {ListNode listNode = null;// 如果map里面没有这个keyif (!map.containsKey(key)){// 如果长度已经满了,就移除一个if (listLen >= capacity){ListNode removeNode = dummyHead.next;removeNode.next.prev = removeNode.prev;removeNode.prev.next = removeNode.next;map.remove(removeNode.key);} else {listLen++;}// 新增一个listNode = new ListNode(key, value);}// 如果map里有这个keyelse {listNode = map.get(key);// 把这个listNode从链表上删除ListNode prev_node = listNode.prev;ListNode next_node = listNode.next;prev_node.next = next_node;next_node.prev = prev_node;listNode.value = value;}// 把这个listNode弄到后面去ListNode insertPre = dummyTail.prev;insertPre.next = listNode;listNode.prev = insertPre;listNode.next = dummyTail;dummyTail.prev = listNode;map.put(key, listNode);}public int get(int key) {if (!map.containsKey(key)){return -1;} else {int result = map.get(key).value;// 拿到这个Node,移除它ListNode listNode = map.get(key);// 把这个listNode从链表上删除ListNode prev_node = listNode.prev;ListNode next_node = listNode.next;prev_node.next = next_node;next_node.prev = prev_node;// 把这个listNode弄到后面去ListNode insertPre = dummyTail.prev;insertPre.next = listNode;listNode.prev = insertPre;listNode.next = dummyTail;dummyTail.prev = listNode;map.put(key, listNode);return result;}}
}/*** 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);*/

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Qwen2技术报告分析】解读模型架构 pre/post数据构建和模型评估

目录 前言 一、Tokenizer 二、模型结构 dense模型 MoE模型 模型参数设置 三、Pre-Training Pre-Training DATA LONG-CONTEXT TRAINING 四、Post-Training Post-Training DATA 人工数据注释&#xff08;collaborative data annotation&#xff09; 自动数据合成&a…

【HarmonyOS】not supported when useNormalizedOHMUrl is not true.

【HarmonyOS】 not supported when useNormalizedOHMUrl is not true. 问题背景&#xff1a; 集成三方库编译时&#xff0c;IDE提示报错信息如下&#xff1a; hvigor ERROR: Bytecode HARs: [cashier_alipay/cashiersdk] not supported when useNormalizedOHMUrl is not true…

pdb和gdb的双剑合璧,在python中调试c代码

左手编程&#xff0c;右手年华。大家好&#xff0c;我是一点&#xff0c;关注我&#xff0c;带你走入编程的世界。 公众号&#xff1a;一点sir&#xff0c;关注领取python编程资料 问题背景 正常情况下&#xff0c;调试python代码用pdb&#xff0c;调试c代码用gdb&#xff0c;…

基于MPPT最大功率跟踪的光伏发电蓄电池控制系统simulink建模与仿真

目录 1.课题概述 2.系统仿真结果 3.核心程序与模型 4.系统原理简介 5.完整工程文件 1.课题概述 基于MPPT最大功率跟踪的光伏发电蓄电池控制系统simulink建模与仿真。本系统包括PV模块&#xff0c;电池模块&#xff0c;电池控制器模块&#xff0c;MPPT模块&#xff0c;PWM模…

uni-app打包后报错云服务空间未关联

使用uni-app打包到h5 项目里面用到了uni-app的云端一体城市选择组件&#xff0c;这个组件数据用到了uniCloud云服务空间&#xff0c;在本地运行没问题&#xff0c;打包之后测试环境报错&#xff1a; 一顿查&#xff0c;查到了官网是这样说的&#xff1a; cli publish --platfo…

vue用jenkins 打包项目项目关闭eslint检查

问题描述&#xff1a;创建vue脚手架项目后&#xff0c;使用jenkins 打包项目&#xff0c;出现如下图所示错误&#xff0c;显示错误来源于eslint检测。 解决方法&#xff1a;在根目录下找到vue.config.js文件&#xff0c;添加lintOnSave: false以关闭eslint检测&#xff0c;项目…

基于Spring Boot的美术馆管理系统的设计与实现,LW+源码+讲解

摘 要 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统美术馆管理系统信息管理难度大&#xff0c;容错率低&…

战略共赢 软硬兼备|云途半导体与知从科技达成战略合作

2024年11月5日&#xff0c;江苏云途半导体有限公司&#xff08;以下简称“云途”或“云途半导体”&#xff09;与上海知从科技有限公司&#xff08;以下简称“知从科技”&#xff09;达成战略合作&#xff0c;共同推动智能汽车领域高端汽车电子应用的开发。 云途半导体与知从科…

【TMM2024】Frequency-Guided Spatial Adaptation for Camouflaged Object Detection

论文链接&#xff1a;https://arxiv.org/abs/2409.12421 这个论文研究 Camouflaged Object Detection &#xff08;COD&#xff09;问题&#xff0c;作者认为&#xff0c;使用 pretrained foundation model 可以改进COD的准确率&#xff0c;但是当前的 adaptor 大多学习空间特…

前端环境配置

对于换公司的小伙伴来讲&#xff0c;重新安装环境&#xff0c;百度或许稍微有点麻烦&#xff0c;本文章让你无脑式直接操作&#xff0c;保证环境畅通无阻。 1.安装nvm-setup 该插件是一款管理nodeJs的包&#xff0c;无需你单独下载nodeJs去安装&#xff0c;只需要下载安装此…

window中借助nginx配置vite+vue项目的反向代理步骤

在官网下载好nginx的安装包后&#xff0c;解压后 CMD打开 start nginx 是启动命令 nginx -s stop 停止服务 nginx -s reload 如果重写了nginx.conf文件&#xff0c;要执行这条命令 正常情况下 成功启动和成功停止服务长这样 错误情况&解决 如果nginx -s stop失败 ngi…

论文阅读:基于语义分割的非结构化田间道路场景识别

论文地址&#xff1a;DOI: 10.11975/j.issn.1002-6819.2021.22.017 概要 环境信息感知是智能农业装备系统自主导航作业的关键技术之一。农业田间道路复杂多变&#xff0c;快速准确地识别可通行区域&#xff0c;辨析障碍物类别&#xff0c;可为农业装备系统高效安全地进行路径规…

【Ant Design Pro】如何实现组件的状态保存umi-plugin-keep-alive插件的使用

都知道vuejs里面帮我们实现了一个内置的keep-alive组件&#xff0c;给我们缓存一些组件的状态带来了很大的便利。但是在react中没有自带的实现&#xff0c;可以借助社区的插件umi-plugin-keep-alive来实现这个功能。 实现效果对比 未使用插件&#xff0c;可以看到我们在页面跳…

Amesim中PID控制元件

PID 控制原理 PID 即比例&#xff08;Proportional&#xff09;、积分&#xff08;Integral&#xff09;、微分&#xff08;Derivative&#xff09;控制。比例环节根据偏差的大小成比例地对系统进行调节&#xff0c;偏差越大&#xff0c;调节作用越强。积分环节用于消除系统的…

SpringBoot框架:共享汽车行业的技术革新

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了共享汽车管理系统的开发全过程。通过分析共享汽车管理系统管理的不足&#xff0c;创建了一个计算机管理共享汽车管理系统的方案。文章介绍了共享汽车管理系统的系…

ASP.NET Core 路由规则,自定义特性路由 ,IActionConstraint 路由约束 总结 mvc

资料 资料 路由服务 路由服务是在 Program.cs 中使用 builder.Services.AddRouting()注册的&#xff0c; 只是默认在 builder 之前已经注册过了&#xff0c;无需我们再次注册。 AddRouting()方法必须在 UseRouting()方法之前运行&#xff0c;它是路由的基础服务。 MapContro…

linux基础——详细篇

免责声明 学习视频来自B 站up主泷羽sec&#xff0c;如涉及侵权马上删除文章。 笔记的只是方便各位师傅学习知识&#xff0c;以下代码、网站只涉及学习内容&#xff0c;其他的都与本人无关&#xff0c;切莫逾越法律红线&#xff0c;否则后果自负。 linux 基础命令重现 cd(切…

Prosre:一款直观的协议发送模拟软件

Proser 是一款直观的协议编辑、发送端模拟软件。 在涉及二进制协议通信的程序开发过程中&#xff0c;我们经常会通过助手类工具编写协议来验证自己的代码&#xff0c;但这些助手对于大协议的编辑非常不友好&#xff0c;这时Proser会协助你轻松的完成测试。 特点 数据直接表达…

常见 HTTP 状态码分类和解释及服务端向前端返回响应时的最完整格式

目前开发的项目很大程度上是为明年的国产化做准备了&#xff0c;所以借这个机会把用了十年的自研系统全部重写&#xff0c;订立更严格的规范&#xff0c;本文记录一下返回格式及对应状态码。 常见 HTTP 状态码及解释 HTTP 状态码用于表示客户端请求的响应状态&#xff0c;它们…

【DL】YOLO11 OBB目标检测 | 模型训练 | 推理

本文进行YOLO11的旋转目标检测任务,旋转目标检测能够更精确地定位和描述那些非水平排列的目标,比如倾斜的飞机、船舶等。在原始的目标检测中,添加一个角度预测,实现定向边界框检测。 话不多说,先来个效果图!!! YOLO11中的旋转目标检测的特点 ▲更精确的定位:通过使用…