LeetCode Hot100 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) 的平均时间复杂度运行。
示例:
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
思路
双向链表维护头尾节点,用哈希表键值对寻找节点
代码
class lrulist
{public:int val;int key;lrulist* next;lrulist* last;lrulist(int value, int k) : val(value), key(k), next(nullptr), last(nullptr){}
};
class LRUCache {
public:unordered_map<int, lrulist*> hashmap;lrulist* back;lrulist* front;int size;int cap;void push_front(int value, int key){lrulist* newnode = new lrulist(value, key);hashmap[key] = newnode;if(front){newnode->next = front;front->last = newnode;}elseback = newnode;front = newnode;++size;}void move(lrulist* node){if(node == front)return;if(back == node){back = back->last;if(back)back->next = nullptr; }else{node->last->next = node->next;node->next->last = node->last; }node->next = front;if(front)front->last = node;front = node;}void del_node(lrulist* node){if(front == node){front = front->next;if(front)front->last = nullptr;}else if(back == node){back = back->last;if(back)back->next = nullptr;}hashmap.erase(node->key);--size;delete node; }LRUCache(int capacity) : size(0), cap(capacity), front(nullptr), back(nullptr){}int get(int key) {if(hashmap.find(key) != hashmap.end()){move(hashmap[key]);return hashmap[key]->val;}elsereturn -1;}void put(int key, int value) {if(hashmap.find(key) == hashmap.end()){if(size == cap)del_node(back);push_front(value, key);}else{hashmap[key]->val = value;move(hashmap[key]);}}
};
相关文章:
LeetCode Hot100 LRU缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -…...
GESP C++ 2024年06月一级真题卷
一、单选题(每题 2 分,共 30 分) 第 1 题 在 C 中,下列不可做变量的是 ( ) 。 A. five-Star B. five_star C. fiveStar D. _fiveStar 答案:A 解析:标识符命名规则,标识符由字母、数…...
在 Ubuntu Server 上配置静态 IP 地址
在 Ubuntu Server 上配置静态 IP 地址 测试时使用的Ubuntu server版本是22.04 一、Ubuntu 17.10之前版本 使用 ifupdown 配置文件来设置静态 IP。配置文件通常位于 /etc/network/interfaces。 1.1 编辑 /etc/network/interfaces 文件: sudo vim /etc/network/in…...
数据结构——栈的讲解(超详细)
前言: 小编已经在前面讲完了链表和顺序表的内容,下面我们继续乘胜追击,开始另一个数据结构:栈的详解,下面跟上小编的脚步,开启今天的学习之路! 目录 1.栈的概念和结构 1.1.栈的概念 1.2.栈的结构…...
三防平板助力MES系统,实现工厂移动式生产报工
在当今竞争激烈的制造业环境中,提高生产效率、优化生产流程以及实现精准的生产管理已经成为企业生存和发展的关键。 MES系统作为连接企业计划层和控制层的桥梁,在实现生产过程的信息化、数字化和智能化方面发挥着重要作用。与此同时,三防平板…...
WEB渗透Bypass篇-常规函数绕过
常规函数绕过 <?php echo exec(whoami);?> ------------------------------------------------------ <?php echo shell_exec(whoami);?> ------------------------------------------------------ <?php system(whoami);?> ------------------------…...
C++从入门到起飞之——string类的模拟实现 全方位剖析!
🌈个人主页:秋风起,再归来~🔥系列专栏:C从入门到起飞 🔖克心守己,律己则安 目录 1、多文件之间的关系 2、模拟实现常用的构造函数 2.1 无参构造函数 2.2 有参的构造函数 2.3 析构函…...
数据库国产化大趋势下,还需要学习Oracle吗?
由于众所周知的原因,近两年各行各业都开始了数据库国产化替代的进程,从国外商业数据库替换到国产或者开源数据库,相信很多的数据库从业人员会把部分精力转移到其他数据库产品的学习中,也有一些人在大肆的宣扬Oracle已经过时了&…...
WebLogic
二、WebLogic 2.1 后台弱口令GetShell 漏洞描述 通过弱口令进入后台界面,上传部署war包,getshell 影响范围 全版本(前提后台存在弱口令) 漏洞复现 默认账号密码:weblogic/Oracle123weblogic常用弱口令: Default Passwords | CIRT.net这里注意&am…...
Aspose.Words.dll 插入模板表格,使用的是邮件合并MailMerge功能,数据源是DataTable或list对象,实例
本实例中的实例功能有: 1、 Aspose.Words.dll 插入模板指定域替换为文字或html标签,见1 2、Aspose.Words.dll 插入模板表格,使用的是邮件合并MailMerge功能,数据源是DataTable或List对象(将list转换成DataTable),见1和2 3、word转换Pdf文件,见1 4、将多个word输出文…...
同时打开多个微信
注: 以下方法用到的 D:\微信\WeChat\WeChat.exe是我的电脑微信路径,可右击桌面微信快捷方式 > 属性 > 目标查看 以下方法都需要先关掉已登录的微信后操作 <一> 找到微信路径 新建一个txt文件输入以下内容 start D:\微信\WeChat\WeChat.exe …...
MPU6050的STM32数据读取
目录 1. 概述2. STM32G030对MPU6050的读取3. STM32F1xx对MPU6050的读取 1. 概述 项目中,往往需要根据不同的环境使用不同的芯片处理某些数据,当使用不同的芯片对六轴陀螺仪芯片MPU6050进行数据处理中,硬件的连接、I/O口的设置往往需要根据相…...
【微信小程序开发】——奶茶点餐小程序的制作(二)
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...
Java 文件上传七牛云
Java系列文章目录 文章目录 Java系列文章目录一、前言二、学习内容:三、问题描述四、解决方案:4.1 新建空间4.2 查找密钥4.3 进入开发者中心查找JavaSDK文档4.4 查找文件上传方法4.5 运行测试 五、总结:5.1 学习总结: 一、前言 学…...
大语言模型生成无人系统(如机械臂、无人机等)可以执行的指令序列
大语言模型生成无人系统(如机械臂、无人机等)可以执行的指令序列涉及将自然语言指令转化为具体的、可执行的指令集合。以下是一个详细的流程,展示了如何从自然语言指令生成无人系统的执行指令序列。 1. 输入自然语言指令 用户输入自然语言指…...
尚硅谷谷粒商城项目笔记——十、调试前端项目renren-fast-vue【电脑CPU:AMD】
十、调试前端项目renren-fast-vue 如果遇到其他问题发在评论区,我看到后解决 1 先下载安装git git官网下载地址 2 登录gitee搜索人人开源找到renren-fast-vue复制下载链接。【网课视频中也有详细步骤】 3 下载完成后桌面会出现renren-fast-vue的文件夹 4 开始调…...
Python 的元组和列表的区别是什么?
以下是 Python 中元组(tuple)和列表(list)的主要区别: 1. 语法表示:元组使用小括号 () 来定义,例如 (1, 2, 3) ;列表使用方括号 [] 来定义,例如 [1, 2, 3] 。 2. 可变性…...
【Impala】学习笔记
Impala学习笔记 【一】Impala介绍【1】简介(1)简介(2)优点(3)缺点 【2】架构(1)Impalad(守护进程)(2)Statestore(存储状态…...
视频汇聚平台EasyCVR接入移动执法记录仪,视频无法播放且报错500是什么原因?
GB28181国标视频汇聚平台EasyCVR视频管理系统以其强大的拓展性、灵活的部署方式、高性能的视频能力和智能化的分析能力,为各行各业的视频监控需求提供了优秀的解决方案。视频智能分析平台EasyCVR支持多协议接入,兼容多类型的设备,包括IPC、NV…...
【Linux基础】Linux基本指令(二)
目录 🚀前言一,mv指令二,more & less指令2.1 more 指令2.1 less指令 三,重定向技术(重要)3.1 echo指令3.2 输出重定向 >3.3 追加重定向 >>3.4 输入重定向 < 四,head & tail指令4.1 head 指令4.2 t…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
