当前位置: 首页 > 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) 的平均时间复杂度运行。

由于我们在维护key-value键值对的同时,还要注意它们的入队顺序,所以用普通的Map肯定是不行的(因为我亲身体验过)

       所以我们需要一个可以自动的维护顺序的数据结构才能处理本题,所以LinikedHashMap肯定是最好的选择,在我们在刷题的时候,其实LinkedHashMap其实是不太常见的,先在这里给大家科普一下:

       LinkedHashMap是一种集合类型,它实现了Map接口,并且通过双向链表维护了插入顺序或者访问顺序,与常规的HashMap相比,LinkedHashMap保持了键值对的插入顺序或访问顺序,这使得它非常适合在按需要按照顺序访问元素的场景中使用

所以要手动的去构建一个结构体,构造方法必不可少

     LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();private int capacity;//容量public LRUCache(int capacity) {this.capacity=capacity;}

       在我们使用的过程中,对于最新访问的key-value,我们无需对其顺序进行改变,但是如果我们去访问了一个比较使用时间过长的key-value,那么每次都要对其键值进行删除增加,这给代码带来非常差的可读性,所以我们应该重新声明一个方法(最近使用recently)

   public void recently(int key){int val=map.get(key);map.remove(key);map.put(key,val);}

       通过key值去获得value的值,如果没有的话直接返回-1,获取值也是一种操作,证明这个key是刚使用过的,所以直接调用函数recnetly()

    public int get(int key) {if(!map.containsKey(key)){return -1;}recently(key);return map.get(key);}

       如果往进put的时候,如果map的key的数量超过capacity,那就直接删除最早进来的key(很久没有使用的key值),直接提升为最近使用,如果没有直接加入

 public void put(int key, int value) {if(map.containsKey(key)){map.put(key,value);recently(key);return;}if(map.size()>=capacity){map.remove(map.keySet().iterator().next());}map.put(key,value);}

在这里给大家着重说明一下keySet().iterator().next()的功能:

keySet():返回LinkedHashMap中的所有键的集合,该方法将返回一个Set的对象,其中包含所有的键

iterator():返回一个迭代器,用于遍历集合中的元素,在这种情况下,我们获取到的是键集合的迭代器,以便逐个访问键

next():迭代器的方法之一,用于获取下一个元素,由于我们希望获得第一个键,所以该操作将返回集合中的第一个元素

       用迭代器遍历集合,当集合初始值不为空时,遍历的过程中是不会抛出异常的,因为集合遍历时用的fail-safe机制,每次遍历的时候,都是拿的原集合一个快照进行遍历,如果当遍历的时候有人对集合进行增删,结果可能就出现了问题

源码借鉴:

  LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();private int capacity;public LRUCache(int capacity) {this.capacity=capacity;}public int get(int key) {if(!map.containsKey(key)){return -1;}recently(key);return map.get(key);}public void put(int key, int value) {if(map.containsKey(key)){map.put(key,value);recently(key);return;}if(map.size()>=capacity){map.remove(map.keySet().iterator().next());}map.put(key,value);}public void recently(int key){int val=map.get(key);map.remove(key);map.put(key,val);}

相关文章:

面试热题(LRU缓存)

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

微信小程序开发【从0到1~入门篇】2023.08

一个小程序主体部分由三个文件组成&#xff0c;必须放在项目的根目录&#xff0c;如下&#xff1a; 文件必须作用app.js是小程序逻辑app.json是小程序公告配置app.wxss否小程序公告样式表 3. 小程序项目结构 一个小程序页面由四个文件组成&#xff0c;分别是&#xff1a; 文…...

P1398 [NOI2013] 书法家

题目描述 输入 #1 3 13 1 1 -1 -1 1 -1 1 1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 1 -1 1 1 1 输出 #1 24 输入 #2 3 13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1…...

【构建卷积神经网络】

构建卷积神经网络 卷积网络中的输入和层与传统神经网络有些区别&#xff0c;需重新设计&#xff0c;训练模块基本一致 全连接层&#xff1a;batch784&#xff0c;各个像素点之间都是没有联系的。 卷积层&#xff1a;batch12828&#xff0c;各个像素点之间是有联系的。 impor…...

SSH 认证原理

SSH协议登录服务器&#xff1a; $ ssh userhost 主要有两种登录方式&#xff1a;第一种为密码口令登录&#xff0c;第二种为公钥登录 密码口令登录 通过密码进行登录&#xff0c;主要流程为&#xff1a; 1、客户端连接上服务器之后&#xff0c;服务器把自己的公钥传给客户端…...

基于DETR (DEtection TRansformer)开发构建MSTAR雷达影像目标检测系统

关于DETR相关的实践在之前的文章中很详细地介绍过&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《DETR (DEtection TRansformer)基于自建数据集开发构建目标检测模型超详细教程》 《书接上文——DETR评估可视化》 基于MSTAR雷达影像数据开发构建目标检测系统&am…...

Java分布式微服务1——注册中心(Eureka/Nacos)

文章目录 基础知识注册中心Eureka注册中心与Ribbon负载均衡1、Eureka注册中心2、Eureka的搭建3、Eureka服务注册4、复制服务实例5、拉取服务6、Ribbon负载均衡的流程及Eureka规则调整&#xff1a;7、Ribbon负载均衡饥饿加载 Nacos注册中心1、服务端Nacos安装与启动2、客户端Nac…...

(文章复现)建筑集成光储系统规划运行综合优化方法matlab代码

参考文献&#xff1a; [1]陈柯蒙,肖曦,田培根等.一种建筑集成光储系统规划运行综合优化方法[J].中国电机工程学报,2023,43(13):5001-5012. 1.基本原理 本文建立的双层耦合模型内、外层分别对应求解容量配置与能量调度问题。外层模型设置光伏与储能容量备选集并将容量配置组合…...

【Redis】——RDB快照

Redis 是内存数据库&#xff0c;但是它为数据的持久化提供了两个技术&#xff0c;一个是AOF日志&#xff0c;另一个是RDB快照&#xff1a; AOF 文件的内容是操作命令&#xff1b;RDB 文件的内容是二进制数据。 RDB 快照就是记录某一个瞬间的内存数据&#xff0c;记录的是实际…...

微服务监控技术skywalking的部署与使用(亲测无坑)

微服务监控技术skywalking的部署与使用 1. 前期准备2. skywalking安装部署2.1 Java Agent2.2 apache/skywalking-oap-server2.3 apache/skywalking-ui 3. 项目启动4.效果展示 1. 前期准备 注&#xff1a;本篇文章采用docker部署&#xff0c;采用8.2.0版本&#xff0c;版本一定…...

DLA 神经网络的极限训练方法:gradient checkpointing

gradient checkpointing 一般来说&#xff0c;训练的过程需要保存中间结果&#xff08;不管是GPU还是CPU&#xff09;。前向传播根据输入(bottom_data)计算输出(top_data)&#xff0c;后向传播由top_diff计算bottom_diff&#xff08;如果某个变量打开梯度进行训练的话&#xff…...

python excel 操作

excel文件内容如下&#xff1a; 一、xlrd 读Excel 操作 1、打开Excel文件读取数据 filexlrd.open_workbook(filename)#文件名以及路径&#xff0c;如果路径或者文件名有中文给前面加一个 r 2、常用函数 &#xff08;1&#xff09;获取一个sheet工作表 table file.sheets(…...

记一次Linux启动Mysql异常解决

文章目录 第一步&#xff1a; netstat -ntlp 查看端口情况2、启动Mysql3、查看MySQL日志 tail -100f /var/log/mysqld.log4、查看磁盘占用情况&#xff1a;df -h5、思路小结 第一步&#xff1a; netstat -ntlp 查看端口情况 并没有发现3306数据库端口 2、启动Mysql service …...

ATFX汇市:美联储年内或仍将加息依次,美指向下空间不大

环球汇市行情摘要—— 昨日&#xff0c;美元指数上涨0.08%&#xff0c;收盘在102.08点&#xff0c; 欧元贬值0.07%&#xff0c;收盘价1.1003点&#xff1b; 日元贬值0.51%&#xff0c;收盘价142.47点&#xff1b; 英镑升值0.28%&#xff0c;收盘价1.2784点&#xff1b; 瑞…...

【博客687】k8s informer的list-watch机制剖析

k8s informer的list-watch机制剖析 1、list-watch场景&#xff1a; client-go中的reflector模块首先会list apiserver获取某个资源的全量信息&#xff0c;然后根据list到的rv来watch资源的增量信息。希望使用client-go编写的控制器组件在与apiserver发生连接异常时&#xff0c…...

用Python获取链家二手房房源数据,做可视化图分析数据

前言 数据采集的步骤是固定: 发送请求, 模拟浏览器对于url地址发送请求获取数据, 获取网页数据内容 --> 请求那个链接地址, 返回服务器响应数据解析数据, 提取我们需要的数据内容保存数据, 保存本地文件 所需模块 win R 输入cmd 输入安装命令 pip install 模块名 (如果你…...

Yield Guild Games:社区更新 — 2023 年第二季度

本文重点介绍了 Yield Guild Games (YGG) 2023 年第二季度社区更新中涵盖的关键主题&#xff0c;包括公会发展计划 (GAP) 第 3 季的总结、YGG 领导团队的新成员以及 YGG 的最新消息地区公会网络和广泛的游戏合作伙伴生态系统。 在 YGG 品牌焕然一新的基础上&#xff0c;第二季…...

Stable Diffusion - 运动服 (Gymwear Leggings) 风格服装与背景的 LoRA 配置

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132179050 测试模型&#xff1a;DreamShaper 8 运动裤 (Gymwear Leggings) 是紧身的裤子&#xff0c;通常用于健身、瑜伽、跑步等运动。运动裤的…...

js-7:javascript原型、原型链及其特点

1、原型 JavaScript常被描述为一种基于原型的语言-每个对象拥有一个原型对象。 当试图访问一个对象的属性时&#xff0c;它不仅仅在该对象上搜寻&#xff0c;还会搜寻该对象的原型&#xff0c;以及该对象的原型的原型&#xff0c;依次层层向上搜索&#xff0c;直到找到一个名字…...

无涯教程-Perl - continue 语句函数

可以在 while 和 foreach 循环中使用continue语句。 continue - 语法 带有 while 循环的 continue 语句的语法如下- while(condition) {statement(s); } continue {statement(s); } 具有 foreach 循环的 continue 语句的语法如下- foreach $a (listA) {statement(s); } co…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; 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 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...