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

算法----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

提示:

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

解决思路

使用Map加双链表实现即可,参考Java里LinkedHashMap

解决方法

    class Node(key: Int, value: Int) {var pre: Node? = nullvar nex: Node? = nullvar value: Intvar key: Intinit {this.value = valuethis.key = key}}class LRUCache(capacity: Int) {var map = mutableMapOf<Int, Node>()private var dumpHead: Node = Node(-1, -1)private var dumpTail: Node = Node(-1, -1)var mCapability = capacityinit {dumpHead.nex = dumpTaildumpTail.pre = dumpHead}fun get(key: Int): Int {val value = map.getOrDefault(key, null)if (value != null) {updateNodeToHeadNext(map[key])}return value?.value ?: -1}fun put(key: Int, value: Int) {if (map.containsKey(key)) {updateNodeToHeadNext(map[key])map[key]!!.value = value} else {val node = Node(key, value)dumpHead.nex!!.pre = nodenode.nex = dumpHead.nexdumpHead.nex = nodenode.pre = dumpHeadmap[key] = node}while (map.size > mCapability) {dumpTail.pre?.let {it.pre!!.nex = dumpTaildumpTail.pre = it.premap.remove(it.key)}}}private fun updateNodeToHeadNext(find: Node?) {if (find != null) {find.nex!!.pre = find.prefind.pre!!.nex = find.nexdumpHead.nex!!.pre = findfind.nex = dumpHead.nexdumpHead.nex = findfind.pre = dumpHead}}}

偷懒版:

    class CacheMap(initialCapacity: Int, loadFactor: Float, accessOrder: Boolean) :LinkedHashMap<Int, Int>(initialCapacity, loadFactor, accessOrder) {private val initC = initialCapacityoverride fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {return size > initC}}class LRUCache(capacity: Int) {var map = CacheMap(capacity, 0.5f, true)fun get(key: Int): Int {return map.getOrDefault(key,-1)}fun put(key: Int, value: Int) {map[key] = value}}

总结

1.事非经过不知难。 本以为很简单 结果还是一个小时下来了

2.哎 之前面试过这个题 但是自己直接说用LinkedHashMap

3.为了保证时间复杂度为O(1),Map 里 value 为 Node
方便对Node进行调整。

相关文章:

算法----LRU缓存机制

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

基于springboot+vue的旅游系统(前后端分离)

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战 主要内容&#xff1a;毕业设计(Javaweb项目|小程序等)、简历模板、学习资料、面试题库、技术咨询 文末联系获取 项目介绍…...

什么是堆栈和队列?如何实现它们?

堆栈&#xff08;Stack&#xff09;和队列&#xff08;Queue&#xff09;是两种常见的线性数据结构&#xff0c;用于组织和管理数据。它们分别具有不同的特点和用途。本文将详细解释堆栈和队列的概念、特点以及如何实现它们。 堆栈&#xff08;Stack&#xff09; 什么是堆栈&…...

编译器自动生成的构造函数

背景 作为一个C小白&#xff0c;最近在看深度解析对象模型的时候&#xff0c;发现一个很久以来的认知错误&#xff1a;编译器会为没有定义构造函数的class生成一个默认构造函数。其实这个观点是错误的&#xff0c;编译器只会在四种情况下生成。 相关知识 一定要明确一个事情…...

SpringSecurity - 认证与授权、自定义失败处理、跨域问题、认证成功/失败处理器

SpringSecurity 文章目录 SpringSecurity一、 简介二、快速入门2.1 maven坐标2.2 访问请求 三、认证与授权3.1 认证3.1.1 登录检验流程3.1.2 SpringSecurity 完整流程3.1.3 认证流程详解3.1.4 校验3.1.5 要解决的问题3.1.6 准备工作3.1.7 实现3.1.7.1 数据库校验用户3.1.7.1.1 …...

自定义映射resultMap

自定义映射resultMap 自定义映射resultMap 自定义映射resultMapresultMap处理字段和属性的映射关系字段名和属性名不一致的情况&#xff0c;如何处理映射关系?1、为查询的字段设置别名&#xff0c;和属性名保持一致2、核心配置文件(mybatis-config.xml)中设置一个全局配置3、使…...

Android修行手册 - Android Studio去掉方法参数提示、变量类型提示、方法引用Usage提示

点击跳转>Unity3D特效百例点击跳转>案例项目实战源码点击跳转>游戏脚本-辅助自动化点击跳转>Android控件全解手册点击跳转>Scratch编程案例点击跳转>软考全系列 &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分享&…...

【车载开发系列】ECU Application Software程序刷新步骤

【车载开发系列】ECU Application Software程序刷新步骤 ECU Application Software程序刷新步骤 【车载开发系列】ECU Application Software程序刷新步骤一. Boot Software&#xff08;引导软件&#xff09;1&#xff09;boot manager&#xff08;启动管理器&#xff09;2&…...

inject和provide的使用

官网介绍用法 V2.2.0 新增的方法 类型 provide&#xff1a;Object | () > Object inject&#xff1a;Array<string> | { [key: string]: string | Symbol | Object }介绍 这对选项需要一起使用&#xff0c;以允许一个祖先组件向其所有子孙后代注入一个依赖&#xff…...

2023年中国研究生数学建模竞赛D题

一、背景介绍 2021年9月22日&#xff0c;中共中央国务院正式发布《关于完整准确全面贯彻新发展理念做好碳达峰碳中和工作的意见》&#xff08;以下简称《意见》&#xff09;&#xff0c;明确了中国双碳行动的顶层设计。 我国是世界上最大的发展中国家&#xff0c;为实现中华民…...

Unity制作曲线进度条

unity制作曲线进度条 大家好&#xff0c;我是阿赵。   在使用Unity引擎做进度条的时候&#xff0c;有时会遇到一个问题&#xff0c;如果进度条不是简单的横向、纵向或者圆形&#xff0c;而是任意的不规则形状&#xff0c;那该怎么办呢&#xff1f;比如这样的&#xff1a; 一…...

面试:C++ 11 智能指针

查询内存泄露方法 啥是内存泄露 内存泄露在维基百科中的解释如下&#xff1a; 在计算机科学中&#xff0c;内存泄漏指由于疏忽或错误造成程序未能释放已经不再使用的内存。内存泄漏并非指内存在物理上的消失&#xff0c;而是应用程序分配某段内存后&#xff0c;由于设计错误&…...

设计模式——3. 抽象工厂模式

1. 说明 抽象工厂模式(Abstract Factory Pattern)是一种创建型设计模式,它提供了一种创建一组相关或依赖对象的方式,而无需指定它们的具体类。抽象工厂模式是工厂模式的扩展,它关注于创建一组相关的对象家族,而不仅仅是一个单一的对象。 抽象工厂模式通常涉及以下几个角…...

vscode 无法使用 compilerPath“D:.../bin/arm-none-eabi-g++.exe”解析配置。

最近在使用vscode搭建ODrive STM32开发环境,依次安装了以下内容: 1.Python3: 用于运行工程构建脚本 2.ST-Link/V2 Drivers: STLink/v2编程器的驱动 3.Visual Studio Code: 轻量级但功能强大的源代码编辑器 …...

Vue.js入门模板语法[上] 及Vue.js实现购物车---详细讲解

前言 前面我们学习了Vue的基础入门&#xff0c;接下来我们学习有关Vue的模板语法&#xff0c;学习Vue语法能提高我们的前端开发效率 Vue.js 使用了基于 HTML 的模板语法&#xff0c;允许开发者声明式地将 DOM 绑定至底层 Vue 实例的数据。所有 Vue.js 的模板都是合法的 HTML &a…...

windows下gvim的配置

一、vim配置文件 "查看自己的vimrc所在的目录 "在命令模式下 :echo $MYVIMRC"打开自己的vimrc文件 "在命令模式下 :e $MYVIMRC 二、排版 "查看自己当前的字体及大小 "在命令模式下 :set guifont?"设置默认的字体为仿宋_GB2312&#xff…...

基于复旦微的FMQL45T900全国产化ARM开发开发套件(核心板+底板)

TES745D是我司自主研制的一款基于上海复旦微电子FMQL45T900的全国产化ARM核心板&#xff08;模块&#xff09;。该核心板将复旦微的FMQL45T900&#xff08;与XILINX的XC7Z045-2FFG900I兼容&#xff09;的最小系统集成在了一个87*117mm的核心板上&#xff0c;可以作为一个核心模…...

Leetcode Top100(23)环形链表

给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置&#xff08;索…...

线性代数基础-行列式

一、行列式之前的概念 1.全排列&#xff1a; 把n个不同的元素排成一列&#xff0c;称为n个元素的全排列&#xff0c;简称排列 &#xff08;实际上就是我们所说的排列组合&#xff0c;符号是A&#xff0c;arrange&#xff09; 2.标准序列&#xff1a; 前一项均小于后一项的序列…...

RT-Thread(学习)

RT-Thread是一款完全由国内团队开发维护的嵌入式实时操作系统&#xff08;RTOS&#xff09;&#xff0c;具有完全的自主知识产权。经过16个年头的沉淀&#xff0c;伴随着物联网的兴起&#xff0c;它正演变成一个功能强大、组件丰富的物联网操作系统。 RT-Thread概述 RT-Threa…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...