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…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
flow_controllers
关键点: 流控制器类型: 同步(Sync):发布操作会阻塞,直到数据被确认发送。异步(Async):发布操作非阻塞,数据发送由后台线程处理。纯同步(PureSync…...
