当前位置: 首页 > news >正文

LeetCode 热题 C++ 146. LRU 缓存

力扣146

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类:

  • LRUCache(int capacity)正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。

函数 getput 必须以 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

提示:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105getput

 思路:

题目比较容易懂,就是数据结构很麻烦()

参考了力扣

评论区的代码。

代码:

class LRUCache {
private:int c;list<pair<int, int>> l;unordered_map<int, list<pair<int, int>>::iterator> m;
public:LRUCache(int capacity) {c=capacity;}int get(int key) {if (m.find(key) == m.end()) return -1;auto k=*m[key];l.erase(m[key]);l.push_front(k);m[key]=l.begin();return k.second;}void put(int key, int value) {if(m.find(key)==m.end()){if(c==l.size()){m.erase(l.back().first);l.pop_back();}}else {l.erase(m[key]);}l.push_front({key, value});m[key] = l.begin();}
};/*** 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);*/

相关文章:

LeetCode 热题 C++ 146. LRU 缓存

力扣146 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中&#xff0c;则返回关键字的值&#xff0c;否…...

Java线程池使用与原理解析(线程池优点、使用方法、参数含义及线程池运转机制)

为什么要使用线程池&#xff1f; JDK1.5后JUC包添加了线程池相关接口&#xff0c;在Java诞生之初并没有线程池这个概念。刚开始Java程序都是自行创建线程去处理任务。随着应用使用的线程越来越多&#xff0c;JDK开发者们发现有必要使用一个统一的类来管理这些线程&#xff0c;…...

mybatis入门配置

mybatis mybatis是一款持久层框架&#xff0c;用于简化JDBC开发 持久层&#xff1a;负责将数据保存到数据库的那一层代码JavaEE的三层架构&#xff1a;表现层、业务层、持久层、&#xff0c;就相当与mvc设计模式过程中的Controller、service、dao 1.创建一个maven模块&#…...

黑客入门(超级详细版)

据我了解&#xff0c;“黑客”大体上应该分为“正”、“邪”两类&#xff0c;正派黑客依靠自己掌握的知识帮助系统管理员找出系统中的漏洞并加以完善&#xff0c;而邪派黑客则是通过各种黑客技能对系统进行攻击、入侵或者做其他一些有害于网络的事情&#xff0c;因为邪派黑客所…...

Java多线程(三)---synchronized、Lock和volatile

Java内存模型&#xff08;非JVM&#xff09;Java内存模型(Java Memory Model简称JMM)&#xff0c;是一种共享内存模型&#xff0c;是多线程的东西&#xff0c;并不是JVM&#xff08;Java Virtual Machine(Java虚拟机)的缩写&#xff09;&#xff0c;这是俩玩意儿&#xff01;&a…...

JVM-Java内存区域

运行时数据区&#xff1a;1、程序计数器&#xff1a;当前线程所执行的字节码指令的行号指示器。在Java虚拟机的概念模型里&#xff0c;字节码解释器的工作就是通过改变这个计数器的值来选取下一条需要执行的字节码指令&#xff0c;它是程序控制流的指示器&#xff0c;分支、循环…...

毕业季,毕业论文查重,paper系列五个免费查重网站推荐

推荐五个常用的免费查重网站 注意&#xff1a; &#xff08;1&#xff09;这些网站基本上都可以通过关注公众号或者转发等来获取免费查重机会&#xff0c;但有些也会有字数限制。每个网站的数据库可能不同&#xff0c;所以建议大家多换几个平台查一查&#xff0c;反正是免费的…...

破解票房之谜:为何高票房电影绕不过“猫眼们”?

如此火爆的春节档很多&#xff0c;如此毁誉参半的春节档鲜有。2023开年&#xff0c;集齐张艺谋、沈腾的《满江红》&#xff0c;以及有票房前作打底的《流浪地球2》接连两部春节档电影票房进入前十&#xff0c;为有些颓靡的中国电影市场注入了一针“强心剂”。与票房同样热闹起来…...

订单服务-----遇到的问题及解决方案

订单服务的问题及解决方案问题1&#xff1a;Feign远程调用时丢失请求头编辑出现这个Feign远程调用时丢失请求头的问题是因为Feign在远程调用的时候会创建一个新的请求&#xff0c;但是这个新的请求里啥都没有&#xff0c;没有cookie值&#xff0c;而这个cookie值里有成功登录后…...

项目经理如何度量项目?及项目度量指标实例【静说】

度量项目是项目经理的一个重要职责&#xff0c;通过度量项目&#xff0c;项目经理可以了解项目的进展情况&#xff0c;及时发现问题并采取相应的措施&#xff0c;以确保项目能够按时、按质、按预算完成。 分享给大家一些常见的项目度量指标&#xff1a; 1. 项目进度&#xff…...

我们应该如何优雅的处理 React 中受控与非受控

引言 大家好&#xff0c;我是19组清风。有段时间没有和大家见面了&#xff0c;最近因为有一些比较重要的事情&#xff08;陪女朋友和换了新公司&#xff09;在忙碌所以销声匿迹了一小段时间&#xff0c; 后续会陆陆续续补充之前构建 & 编译系列中缺失的部分&#xff0c;提…...

力扣热题100Day06:20. 有效的括号,21. 合并两个有序链表,22. 括号生成

20. 有效的括号 题目链接&#xff1a;20. 有效的括号 - 力扣&#xff08;Leetcode&#xff09; 思路&#xff1a;使用栈 &#xff08;1&#xff09;遇到左括号就将其对应的右括号压入到栈中 &#xff08;2&#xff09;如果遇到右括号 a. 如果弹出的元素与当前不等&#xff…...

【Yolov5】保姆级别源码讲解之-推理部分detect.py文件

推理部分之detect.py文件讲解1.下载Yolov5的源码2. 主函数讲解3.文件标头的注释4. main函数的5. run函数5.1 第一块参数部分5.2第二块&#xff0c;传入数据预处理5.3 第三块创建文件夹5.4 第四块 加载模型的权重5.5 第五块 Dataloader 加载模块5.6 第六块 推理部分 Run inferen…...

无重叠区间-力扣435-java贪心策略

一、题目描述给定一个区间的集合 intervals &#xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量&#xff0c;使剩余区间互不重叠 。示例 1:输入: intervals [[1,2],[2,3],[3,4],[1,3]]输出: 1解释: 移除 [1,3] 后&#xff0c;剩下的区间没有重叠。…...

Python使用VTK对容积超声图像进行体绘制(三维重建)

目录VTK简介什么是体绘制&#xff1f;体绘制效果图流程CodeQ&AReferenceVTK简介 VTK&#xff08;Visualization Toolkit&#xff09;是一个用于3D计算机图形学、图像处理和可视化的开源软件包。它包括一组C类和工具&#xff0c;可以让用户创建和处理复杂的3D图形和数据可视…...

JAVA设计模式之工厂模式讲解

目录 前言 开始表演 前言 Java中使用工厂模式的主要原因是为了实现代码的灵活性和可维护性。工厂模式是一种创建型设计模式&#xff0c;它提供了一种将对象的创建和使用进行分离的方式。具体来说&#xff0c;工厂模式可以将对象的创建过程封装在一个独立的工厂类中&#xff…...

近万字概述L3及以上自动驾驶故障运行和故障安全机制

本文描述了对ADS的FO和FS机制的评估方法。当系统不能按预期运行时,ADS将使用FO和FS机制。这些机制使ADS能够在最大程度上达到使车辆及其乘员脱离危险的MRC。定义、测试和验证实现MRC的FO和FS策略是确保ADS安全运行和部署的重要步骤。 MRC在SAE J3016中被定义为: 用户或ADS在…...

kafka入门到精通

文章目录一、kafka概述&#xff1f;1.定义1.2消息队列1.2.1 传统消息队列的使用场景1.2.2 消息队列好处1.2.3 消息队列两种模式1.3 kafka基础架构二、kafka快速入门1.1使用docker-compose安装kafka1.2测试访问kafka-manager1.3 查看kafka版本号1.4 查看zookeeper版本号1.5 扩展…...

es-09模糊查询

模糊查询 前缀搜索&#xff1a;prefix 概念&#xff1a;以xx开头的搜索&#xff0c;不计算相关度评分。 注意&#xff1a; 前缀搜索匹配的是term&#xff0c;而不是field。前缀搜索的性能很差前缀搜索没有缓存前缀搜索尽可能把前缀长度设置的更长 语法&#xff1a; GET <ind…...

57 - 深入解析任务调度

---- 整理自狄泰软件唐佐林老师课程 文章目录1. 问题1.1 思考1.2 实例分析&#xff1a;问题分析及解决2. 深入讨论2.1 任务调度的定义2.2 关于调度算法的分类2.3 什么时候进行任务调度2.4 任务的分类2.5 关于优先级调度2.6 问题2.7 调度算法的终极目标2.8 课后扩展1. 问题 系统…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...