leetcode hot100 LRU缓存
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) 的平均时间复杂度运行。
class ListNode(object):
def __init__(self,key,val,next=None,prev=None):
self.val =val
self.key = key
self.next = next
self.prev = prev
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.head = ListNode(-1,-1,None,None)
self.tail = ListNode(-1,-1,None,None)
self.head.next=self.tail
self.tail.prev = self.head
self.num_nodes = 0
self.hashmap={}
# 应该是保存key ：node node里面是val
def remove_to_tail(self,rt):
rt.prev.next = rt.next
rt.next.prev = rt.prev
# 放到末尾，这里有点问题，应为删除的可能就是末尾
prev = self.tail.prev
prev.next = rt
rt.next = self.tail
self.tail.prev = rt
rt.prev = prev
def get(self, key):
"""
:type key: int
:rtype: int
"""
# 转移到链表的尾部
rt = self.hashmap.get(key,-1)
if rt==-1:
# 找不到的话，那就return -1
return -1
else:
# 能找到就找到并且放到末尾
# 删除原本的，然后放到末尾
# 如果是末尾的话，根本不用动
if rt==self.tail.prev:
return rt.val
else:
# 删除原本的
self.remove_to_tail(rt)
return rt.val
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if self.hashmap.get(key):
# print(1111111)
self.hashmap[key].val = value
# 然后放到tail去
rt = self.hashmap[key]
# 删除原本的
self.remove_to_tail(rt)
else:
temp = ListNode(key,value)
if self.num_nodes<self.capacity:
self.hashmap[key]=temp
prev = self.tail.prev
prev.next = temp
temp.next = self.tail
self.tail.prev = temp
temp.prev = prev
self.num_nodes+=1
else:
# >=cap,也就是需要我们来删除一个
# 删除头结点的下一个节点
dele = self.head.next
self.head.next = dele.next
dele.next.prev = self.head
# hashmap里面也要删除
# print(self.hashmap)
# print(dele.key)
del self.hashmap[dele.key]
# 删除之后加上最新的到为节点
self.hashmap[key]=temp
prev = self.tail.prev
prev.next = temp
temp.next = self.tail
self.tail.prev = temp
temp.prev = prev
# 如果input的是相同的key会覆盖掉，这个时候num_nodes-1
if key == dele.key:
self.num_nodes-=1
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
这里我们的思路是，放入需要o1那么直接的我们使用hashmap，key是key value是list节点，同时节点要存储key和value，因为要通过节点进行删除，如果只有value，那就无法再hashmap之中删除
根据LRU的规律我们选择双向链表，因为单向的没有prev和next，无法进行删除操作
需要对于LRU算法非常熟悉才行啊，比如说
插入的时候：
如果没到存储上限，那就直接放到最近使用
如果到达存储上限，那就删除掉最远的，放到最近使用
如果插入的是已经有的，那就把原本的换成现在的，并且放到最近使用
查询：
如果查询到了，把原本节点删除，新节点直接放到最近使用
一些细节：必须要有两个伪装节点head tail因为如果这两个不单独创建的话，删除的时候tail很可能被删除，不好写
相关文章：
leetcode hot100 LRU缓存
146. LRU 缓存 已解答 中等 相关标签 相关企业 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中&…...
什么是DDoS攻击?如何防范DDoS攻击?
定义 DDoS（Distributed Denial of Service）攻击全称为分布式拒绝服务攻击。它是一种恶意的网络攻击手段，攻击者通过控制大量的计算机（这些计算机通常被称为“僵尸主机”或“肉鸡”），同时向目标服务器或网络…...
使用 Dash 构建交互式数据可视化应用
使用 Dash 构建交互式数据可视化应用 1. 什么是 Dash？ Dash 是一个由 Plotly 开发的开源 Python 框架，用于快速构建交互式数据可视化应用。Dash 将前端（HTML、CSS 和 JavaScript）与后端（Python）无缝集成&…...
【Linux网络编程】第十五弹---传输层深度解析：端口号划分、UDP协议特性与TCP协议全面剖析（含连接管理、流量控制、拥塞控制等）
✨个人主页： 熬夜学编程的小林 💗系列专栏： 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【Linux网络编程】 目录 1、传输层 1.1、再谈端口号 1.1.1、端口号范围划分 1.1.2、认识知名端口号 1.1.3、两个问题 1.2、UDP …...
SQL语句整理五-StarRocks
文章目录 查看版本号：SPLIT：insert 和 update 结合 select：报错：1064 - StarRocks planner use long time 3000 ms in memo phase：字段增删改： 查看版本号： select current_version(); current…...
【GIS教程】使用GDAL实现栅格转矢量（GeoJSON、Shapefile）- 附完整代码
文章目录 一、 应用场景1、GeoJSON2、ESRI Shapefile3、GDAL 二、基本思路1、数据准备2、重投影（可选）3、创建空的矢量图层4、栅格转矢量 三、完整代码四、总结五、拓展（使用ArcGIS工具进行栅格转矢量） 一、 应用场景 TIFF格式的…...
美国加州房价数据分析02
5. 特征工程 5.1重构数据集 承接上文提到的相似度排名，去掉部分无关的特征。 train_set.corr()["median_house_value"].sort_values(ascendingFalse)为了提高模型训练后的鲁棒性，即防止过拟合，不建议删除关联度最低几项特征&#…...
[安徽省赛 2021]misc签到
给了一个图片，改成jpg格式，查看属性 发现备注 this_is_password 这可能是密码什么东西的 把图片拉到kali里面用用工具binwalk工具分离 发现了flag.txt文件 把压缩包拉到windows系统中 解压，输入密码 得到flag NSSCTF{ab32056rfanla12380a…...
LeetCode：1705. 吃苹果的最大数目（优先级队列 + 贪心 Java）
目录 1705. 吃苹果的最大数目 题目描述： 实现代码与解析： 优先级队列 贪心 原理思路： 1705. 吃苹果的最大数目 题目描述： 有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天&#x…...
MX3200显微尺寸测量仪
产品简介 MX3200显微尺寸测量仪将显微成像与传统影像测量相结合，实现了微小特征的大范围测量。配置电动塔台，可自动切换到不同的倍率，探测各种精密微观二维尺寸特征。尺寸测量功能丰富，可进行各种二维尺寸点、线、圆等的测量和形…...
VR 动感单车身心调适系统的功能与作用
如今，人们面临着来自各方的压力，国家重视国民身心健康，但人们在实际生活中却缺乏有效的身心调节方式。无论是久坐的白领，还是学业繁重的学生，都存在身体亚健康和心理压力大的问题。传统健身方式枯燥、心理咨询成本高且…...
LabVIEW伸缩臂参数监控系统
LabVIEW开发伸缩臂越野叉车参数监控系统主要应用于工程机械中的越野叉车，以提高车辆的作业效率和故障诊断能力。系统通过PEAK CAN硬件接口和LabVIEW软件平台实现对叉车作业参数的实时监控和故障分析，具有良好的实用性和推广价值。 系统组成 系统主要由P…...
Spring提供了很好事务管理机制
事务管理在系统开发中是不可缺少的一部分，Spring提供了很好事务管理机制 分类 主要分为编程式事务和声明式事务两种。 编程式事务 是指在代码中手动的管理事务的提交、回滚等操作，代码侵入性比较强，如下示例： try {//TODO so…...
Selenium 和 Playwright两大框架的不同之处
自动化测试工具百花齐放，其中 Selenium 和 Playwright 是两大热门框架，谁才是你的最佳选择？面对企业项目的真实需求，它们的差异究竟在哪儿？ Selenium 和 Playwright 是两种流行的自动化测试工具，它们都被用…...
【计算机视觉】轮廓检测
一、轮廓检测 在计算机视觉中，轮廓检测是另一个比较重要的任务，不单是用来检测图像或者视频帧中物体的轮廓，而且还有其他操作与轮廓检测相关。 以下代码展示了如何使用 OpenCV 进行 图像阈值处理、寻找图像轮廓 和 绘制轮廓 的完整流程&…...
【Linux】深入Linux：GCC/G++编译器实用指南
Linux相关知识点可以通过点击以下链接进行学习一起加油！初识指令指令进阶权限管理yum包管理与vim编辑器 在Linux系统中，理解和掌握GCC/G编译器是开发者不可或缺的技能之一。本文将深入探讨它们的工作原理和实际运用，帮助读者更好地利用这些强…...
【未来编程：AI如何通过合成复用原则优化设计】
🌈个人主页: Aileen_0v0 🔥热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 💫个人格言:“没有罗马,那就自己创造罗马~” 文章目录 前言合成复用原则含义 继承复用含义UML图实现代码运行结果及分析优缺点 合成复用（我有这…...
)
【Rust自学】5.3. struct的方法(Method)
喜欢的话别忘了点赞、收藏加关注哦，对接下来的教程有兴趣的可以关注专栏。谢谢喵！(･ω･) 5.3.1. 什么是方法(Method) 方法和函数类似，也是用fn关键字进行声明，方法也有名称，也有参数ÿ…...
单片机 STM32入门
一、什么是单片机 单片机（Microcontroller Unit，MCU）是一种集成电路芯片，它将计算机的CPU、存储器（包括RAM和ROM）、输入/输出接口等集成在一个芯片上。单片机通常用于嵌入式系统，能够执行特定的…...
OneCode：开启高效编程新时代——企业定制出码手册
一、概述 OneCode 的 DSM（领域特定建模）出码模块是一个强大的工具，它支持多种建模方式，并具有强大的模型转换与集成能力，能够提升开发效率和代码质量，同时方便团队协作与知识传承，还具备方便的仿…...
学python还是学java？哪个相对来说比较容易上手?
在比较Python和Java哪个更容易上手时，可以从多个维度进行分析，包括语法简洁性、学习资源、应用领域、学习曲线等。 一、语法简洁性 Python：Python的语法简洁明了，更接近自然语言，易于理解和记忆。它使用缩进来表示代…...
C语言项目 天天酷跑（上篇）
前言 这里讲述这个天天酷跑是怎么实现的，我会在天天酷跑的下篇添加源代码，这里会讲述天天酷跑这个项目是如何实现的每一个思路，都是作者自己学习于别人的代码而创作的项目和思路，这个代码和网上有些许不一样，因为掺杂了…...
Windows 11 安装 Dify 完整指南 非docker环境
# Windows 11 安装 Dify 完整指南## 前置要求- Python 3.11 - Node.js 18 - PostgreSQL 14 - Redis for Windows - Git - Ollama (可选，用于本地模型)## 详细安装步骤### 1. 安装必要软件1. **Python 3.11**- 从 https://www.python.org/downloads/release/python-…...
MySQL变量
文章目录 MySQL变量系统变量查看系统变量设置系统变量 自定义变量用户变量局部变量 MySQL变量 MySQL变量分为系统变量和自定义变量 系统变量 系统变量有全局变量和会话变量 查看系统变量 #查看全局系统变量 show global variables; #根据条件查询全局系统变量 show global …...
Ubuntu离线安装Docker容器
前言 使用安装的工具snap安装在沙箱中，并且该沙箱之外的权限有限。docker无法从其隔离的沙箱环境访问外部文件系统。 目录 前言准备环境卸载已安装的Docker环境快照安装的Dockerapt删除Docker 安装docker-compose下载执行文件将文件移到 /usr/local/bin赋予执行权限…...
ensp 关于acl的运用和讲解
ACL（Access Control List，访问控制列表）是一种常用于网络设备（如路由器、交换机）上的安全机制，用于控制数据包的流动与访问权限。ACL 可以指定哪些数据包允许进入或离开某个网络接口，基于不同的…...
yum源配置)
Linux(Centos 7.6)yum源配置
yum是rpm包的管理工具，可以自动安装、升级、删除软件包的功能，可以自动解决软件包之间的依赖关系，使得用户更方便软件包的管理。要使用yum必须要进行配置，个人将其分为三类，本地yum源、局域网yum源、第三方yum源&#…...
[WASAPI]音频API:从Qt MultipleMedia走到WASAPI，相似与不同
[WASAPI] 从Qt MultipleMedia 来看WASAPI 最近在学习有关Windows上的音频驱动相关的知识，在正式开始说WASAPI之前，我想先说一说Qt的Multiple Media，为什么呢？因为Qt的MultipleMedia实际上是WASAPI的一层封装，它在是线…...
什么是MVCC？
MVCC（多版本并发控制，Multi-Version Concurrency Control）是一种用于数据库管理系统中的并发控制的技术。它允许多个事务同时对同一数据进行读取和修改，而不会相互干扰，从而提高了数据库的并发性能。以下是对MVCC的详细…...
C/C++基础错题归纳
文章目录 第1天1.下面程序段的运行结果是：答案知识补充 2.当一个类A 中没有声明任何成员变量与成员函数,这时sizeof(A)的值是多少？答案知识补充 3.下面程序输出是什么?答案其他讲解 第1天 1.下面程序段的运行结果是： char C[5]{‘a’,’b’…...
Nginx 常用安全头
Web 应用中配置 HTTP 安全响应头是提升网站安全性的重要一步。合理配置 Nginx 的安全头，可以抵御常见的安全威胁（如 XSS、点击劫持、MIME 类型嗅探等），增强用户隐私保护和传输安全性。 常见的 HTTP 安全头及其作用 1. Content-Se…...
消息队列（一）消息队列的工作流程
什么是消息队列 首先，代入一个场景，我现在做一个多系统的集成，分别有系统A、B、C、D四个系统，A系统因为使用产生了业务数据，B、C、D需要使用这些数据做相关的业务处理和运算，最基本的做法就是通过接口通信…...
LeetCode 2605 从两个数字数组里生成最小数字
探寻两个数组数位关联下的最小数字问题 题目描述 给定两个只包含 1 到 9 之间数字的数组 nums1 和 nums2，并且每个数组中的元素都是互不相同的。我们需要返回最小的数字，要求这个数字满足两个数组都至少包含这个数字的某个数位。例如，若 nu…...
AI新书推荐：深度学习和大模型原理与实践（清华社）
本书简介 在这个信息爆炸、技术革新日新月异的时代，深度学习作为人工智能领域的重要分支，正引领着新一轮的技术革命。《深度学习和大模型原理与实践》一书，旨在为读者提供深度学习及其大模型技术的全面知识和实践应用的指南。 本书特色在于…...
32单片机串口数据接收、空闲IDLE中断详解
一、前提说明 一开始写单片机程序的时候不太清楚空闲中断这个东西，每次用串口接收数据，都要再开一个定时器，在定时器内进行倒计时，每次接收数据就重置计时时间，计时结束就触发中断，再判断所有接收的数据&am…...
WebRtc webrtc-streamer部署
文章目录 本文档只是为了留档方便以后工作运维，或者给同事分享文档内容比较简陋命令也不是特别全，不适合小白观看，如有不懂可以私信，上班期间都是在得 WebRtc webrtc-streamer 部署 docker run -p 8000:8000 -it mpromonet/webrt…...
shiro注入filter内存马（绕过长度限制）
shiro环境 https://github.com/yyhuni/shiroMemshell（实验环境） 这里用的 Client_memshell.java package com.example.demo;import javassist.ClassPool; import javassist.CtClass; import org.apache.shiro.crypto.AesCipherService; import org.ap…...
Springboot + vue3 实现大文件上传方案：秒传、断点续传、分片上传、前端异步上传
参考：https://juejin.cn/post/6870837414852886542#heading-9 一般计算大文件的md5都是前端来做，因为如果后端来做，那得等到上传成功后才能计算md5值，并且读取的时间也很长。 为了解决文件大传输慢的问题，前端可以通…...
渗透Vulnhub-DC-9靶机
本篇文章旨在为网络安全渗透测试行业靶机教学。通过阅读本文，读者将能够对渗透Vulnhub系列DC-6靶机有定的了解 一、信息收集阶段 DC-9靶场信息: DC-9靶场介绍： https://www.vulnhub.com/entry/dc-9,412/ DC-9靶场下载： https://download.vu…...
_kaic)
springboot477基于vue技术的农业设备租赁系统(论文+源码)_kaic
摘 要 使用旧方法对农业设备租赁系统的信息进行系统化管理已经不再让人们信赖了，把现在的网络信息技术运用在农业设备租赁系统的管理上面可以解决许多信息管理上面的难题，比如处理数据时间很长，数据存在错误不能及时纠正等问题。这次开发的农…...
CentOS常见命令
CentOS（Community ENTerprise Operating System）基于Red Hat Enterprise Linux（RHEL）源代码开发，是常用的Linux发行版之一。在CentOS系统中，有许多命令用于管理和操作系统，以下是一些CentOS系统…...
oracle 设置归档日志存放路径
oracle 设置归档日志存放路径 1、创建新目录 mkdir /archive chown -R oracle:oinstall /archive 注：条件允许的话，/archive 目录应独立挂载。1、便于监控目录使用率；2、避免和其它文件混淆，便于管理。 2、设置归档日志存放路…...
机器学习1-简单神经网络
相比传统的机器学习算法，深度学习做出了哪些改进呢？其实两者在理论结构上是一致的，即：模型假设、评价函数和优化算法，其根本差别在于假设的复杂度 构建简单神经网络（未训练）： # 封装…...
C++的侵入式链表
非侵入式链表 非侵入式链表是一种链表数据结构，其中每个元素（节点）并不需要自己包含指向前后节点的指针。链表的结构和节点的存储是分开的，链表容器会单独管理这些指针。 常见的非侵入式链表节点可以由以下所示，即&a…...
MFC案例：图片文件转图标（ico）格式
本案例程序目的是将一般图像文件转换成图标格式(ico)。实现起来不是很复杂，这里为了介绍MFC的具体使用方法，在程序界面上分成几个功能块，包括：打开图像文件、选择ICON大小、转换、预览、保存等。相关具体步骤如下： 一、…...
【从零开始入门unity游戏开发之——unity篇02】unity6基础入门——软件下载安装、Unity Hub配置、安装unity编辑器、许可证管理
文章目录 一、软件下载安装1、Unity官网2、下载Unity Hub 二、修改Unity Hub配置1、设置Unity Hub中文语言2、修改默认存储目录 三、安装unity编辑器1、点击安装编辑器2、版本选择3、关于版本号4、安装模块选择5、等待下载完成自动安装即可6、追加unity和模块 四、许可证管理专…...
东子生物完成A轮战略融资，数字商品交易全新升级为数商时代
2024年11月23日，东子生物数字时代正式上线，标志着公司全面迈入“数商时代”，作为国内领先的生物科技企业，东子生物在数字化浪潮中精准布局，以创新科技推动产业升级，以全新的思维引领健康产业，兼…...
数据结构经典算法总复习（上卷）
第一章：数据结构导论 无重要考点，仅需了解时间复杂度。 第二章：线性表 1.获得线性表第i个元素 void GetElem_sq(SqList L, int i, ElemType &e) {if (i<1 || i>L.length) ErrorMsg("Invalid i value"); //注意错误监…...
电脑使用CDR时弹出错误“计算机丢失mfc140u.dll”是什么原因?“计算机丢失mfc140u.dll”要怎么解决？
电脑使用CDR时弹出“计算机丢失mfc140u.dll”错误：原因与解决方案 在日常电脑使用中，我们时常会遇到各种系统报错和文件丢失问题。特别是当我们使用某些特定软件，如CorelDRAW（简称CDR）时，可能会遇到“计算…...
oracle使用imp命令导入dmp文件
需求： 增量导入 tbl_servicelegalclause 表数据（dmp格式）。 导入思路：使用 dba 创建一个 临时库，先将 tbl_servicelegalclause.dmp（增量的数据） 文件导入到 临时库，然后确认临时库数…...