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

LeetCode(65)LRU 缓存【链表】【中等】

在这里插入图片描述

目录

    • 1.题目
    • 2.答案
    • 3.提交结果截图

链接: LRU 缓存

1.题目

请你设计并实现一个满足 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 <= 10^5
  • 最多调用 2 * 10^5getput

2.答案

class LRUCache {private Integer capacity;private Map<Integer, Integer> valueMap;private Queue<Integer> queue;public LRUCache(int capacity) {this.capacity = capacity;valueMap = new HashMap<>(capacity);queue = new ArrayDeque<>(capacity);}public int get(int key) {if (valueMap.containsKey(key)) {Integer value = valueMap.get(key);queue.remove(key);queue.offer(key);return value;} else {return -1;}}public void put(int key, int value) {Integer oldValue = valueMap.put(key, value);if (oldValue == null) {// 新增queue.offer(key);if (queue.size() > capacity) {// 逐出最久未使用的关键字Integer oldKey = queue.poll();valueMap.remove(oldKey);}} else {// 替换queue.remove(key);queue.offer(key);}}
}/*** 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);*/

3.提交结果截图

在这里插入图片描述

整理完毕,完结撒花~ 🌻

相关文章:

LeetCode(65)LRU 缓存【链表】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; LRU 缓存 1.题目 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 k…...

网站提示“不安全”

当你在浏览网站时&#xff0c;有时可能会遇到浏览器提示网站不安全的情况。这通常是由于网站缺乏SSL证书所致。那么&#xff0c;从SSL证书的角度出发&#xff0c;我们应该如何解决这个问题呢&#xff1f; 首先&#xff0c;让我们简单了解一下SSL证书。SSL证书是一种用于保护网站…...

【Linux】驱动

驱动 驱动程序过程 系统调用 用户空间 内核空间 添加驱动和调用驱动 驱动程序是如何调用设备硬件 驱动 在计算机领域&#xff0c;驱动&#xff08;Driver&#xff09;是一种软件&#xff0c;它充当硬件设备与操作系统之间的桥梁&#xff0c;允许它们进行通信和协同工作。驱动程…...

Java研学-HTML

HTML 1 介绍 HTML(Hypertext Markup Language) 超文本标记语言。静态网页&#xff0c;用于在浏览器上显示数据 超文本: 指页面内可以包含图片、链接&#xff0c;甚至音乐、程序等非文字元素。 标记语言: 使用 < > 括起来的语言 超文本标记语言的结构, 包括“头”部分&am…...

SpringBoot之响应的详细解析

2. 响应 前面我们学习过HTTL协议的交互方式&#xff1a;请求响应模式&#xff08;有请求就有响应&#xff09; 那么Controller程序呢&#xff0c;除了接收请求外&#xff0c;还可以进行响应。 2.1 ResponseBody 在我们前面所编写的controller方法中&#xff0c;都已经设置了…...

redis:四、双写一致性的原理和解决方案(延时双删、分布式锁、异步通知MQ/canal)、面试回答模板

双写一致性 场景导入 如果现在有个数据要更新&#xff0c;是先删除缓存&#xff0c;还是先操作数据库呢&#xff1f;当多个线程同时进行访问数据的操作&#xff0c;又是什么情况呢&#xff1f; 以先删除缓存&#xff0c;再操作数据库为例 多个线程运行的正常的流程应该如下…...

智能优化算法应用:基于动物迁徙算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于动物迁徙算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于动物迁徙算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.动物迁徙算法4.实验参数设定5.算法结果6.…...

illuminate/database 使用 五

之前文章&#xff1a; illuminate/database 使用 一-CSDN博客 illuminate/database 使用 二-CSDN博客 illuminate/database 使用 三-CSDN博客 illuminate/database 使用 四-CSDN博客 一、原生查询 1.1 原理 根据之前内容调用执行的静态类为Illuminate\Database\Capsule\M…...

武汉灰京文化:益智游戏的教育与娱乐完美结合

随着游戏技术的不断发展&#xff0c;益智类游戏正经历着一场革命性的变革&#xff0c;逐渐融合了教育和娱乐的元素。创新的设计和互动方式使得许多益智游戏成为了知识传递和技能训练的有效工具&#xff0c;同时保持了娱乐体验的趣味性。这种教育与娱乐的完美结合不仅使益智游戏…...

arcgis api for js 中的query实现数据查询

相当于服务地址中的query查询 获取图层范围内的数据4.24 import Query from arcgis/core/rest/support/Query; import * as QueryTask from "arcgis/core/rest/query";//获取图层范围内的数据4.24 _returnFeatureFromWhere(url, where, geo) {const self thisretu…...

AcWing 1250. 格子游戏(并查集)

题目链接 活动 - AcWing本课程系统讲解常用算法与数据结构的应用方式与技巧。https://www.acwing.com/problem/content/1252/ 题解 当两个点已经是在同一个连通块中&#xff0c;再连一条边&#xff0c;就围成一个封闭的圈。一般用x * n y的形式将&#xff08;x, y&#xff0…...

CSS对文本的简单修饰

CSS格式&#xff1a; 格式一&#xff1a;在head中的style标签范围内。 < style> 在style内的只写名字不写 &#xff1a; < > 选择器 { 属性的名称 &#xff1a; 样式&#xff1b; 属性的名称&#xff1a;样式&#xff1b; } < style> style中的注释用/* *…...

C++17中if和switch语句的新特性

1.从C17开始&#xff0c;if语句允许在条件表达式里添加一条初始化语句。当仅在if语句范围内需要变量时&#xff0c;使用这种形式的if语句。在if语句的条件表达式里定义的变量将在整个if语句中有效&#xff0c;包括else部分。 std::mutex mx; bool shared_flag true; // guard…...

极坐标下的牛拉法潮流计算57节点MATLAB程序

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 潮流计算&#xff1a; 潮流计算是根据给定的电网结构、参数和发电机、负荷等元件的运行条件&#xff0c;确定电力系统各部分稳态运行状态参数的计算。通常给定的运行条件有系统中各电源和负荷点的功率、枢纽…...

软件设计师——计算机网络(三)

&#x1f4d1;前言 本文主要是【计算机网络】——软件设计师——计算机网络的文章&#xff0c;如果有什么需要改进的地方还请大佬指出⛺️ &#x1f3ac;作者简介&#xff1a;大家好&#xff0c;我是听风与他&#x1f947; ☁️博客首页&#xff1a;CSDN主页听风与他 &#x1…...

【ArkTS】循环控制与List的使用

ArkTS如何进行循环渲染 现有数据如下 class Item{name:stringimage:Resourceprice:numberdicount:numberconstructor(name:string,image:Resource,price:number,dicount?:number) {this.name namethis.image imagethis.price pricethis.dicount dicount} }private items…...

条款3:尽量使用const

文章目录 const指针和函数声明const修饰指针const修饰函数const修饰容器const应用在函数中 const限定成员函数避免const重载的代码重复总结 const指针和函数声明 const修饰指针 char greeting[] "Hello"; char* p greeting; // non-const 指针,// non-const 数据…...

Chromadb词向量数据库总结

简介 Chroma 词向量数据库是一个用于自然语言处理&#xff08;NLP&#xff09;和机器学习的工具&#xff0c;它主要用于词嵌入&#xff08;word embeddings&#xff09;。词向量是将单词转换为向量表示的技术&#xff0c;可以捕获单词之间的语义和语法关系&#xff0c;使得计算…...

Gin之GORM 操作数据库(MySQL)

GORM 简单介绍 GORM 是 Golang 的一个 orm 框架。简单说&#xff0c;ORM 就是通过实例对象的语法&#xff0c;完成关系型数据库的操作的技术&#xff0c;是"对象-关系映射"&#xff08;Object/Relational Mapping&#xff09; 的缩写。使用 ORM框架可以让我们更方便…...

二十七、读写文件

二十七、读写文件 27.1 文件类QFile #include <QCoreApplication>#include<QFile> #include<QDebug>int main(int argc, char *argv[]) {QCoreApplication a(argc, argv);QFile file("D:/main.txt");if(!file.open(QIODevice::WriteOnly | QIODe…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...