Java算法_ LRU 缓存(LeetCode_Hot100)
题目描述:请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
获得更多?算法思路:代码文档,算法解析的私得。
运行效果
完整代码
import java.util.HashMap;
import java.util.Map;/*** 2 * @Author: LJJ* 3 * @Date: 2023/8/7 13:14* 4*/
public class LRUCache {class Node{int key;String value;Node prev;Node next;public Node(int key , String value){this.key = key;this.value = value;}}private int capacity;private Map<Integer,Node> cache;private Node head;private Node tail;// 初始化LRUCache类的构造函数,// 使用了一个哨兵节点的技巧,将head和tail初始化为哨兵节点,并不存储具体的键值对。// 哨兵节点可以简化链表的操作,避免处理头部和尾部节点时需要特殊处理的情况。public LRUCache(int capacity){this.capacity = capacity;cache = new HashMap<>();//初始化头尾节点;head = new Node(-1, "-1");tail = new Node(-1, "-1");head.next = tail;tail.prev = head;}public String get(int key){if (cache.containsKey(key)){Node node = cache.get(key);//将查到的节点移动到链表头部removeNode(node);addToHead(node);return node.value;}return "-1";}public void put(int key, String value){if (cache.containsKey(key)){Node node = cache.get(key);node.value = value;//将更新后的节点移动到链表头部removeNode(node);addToHead(node);}else {if (cache.size() >= capacity){//如果缓存已满,需要移除最久未使用的节点(即链表尾部节点)cache.remove(tail.prev.key);removeNode(tail.prev);}Node newNode = new Node(key,value);cache.put(key,newNode);//将新的节点插入链表头部addToHead(newNode);}}// 将节点插入链表头部private void addToHead(Node node){node.next = head.next;head.next.prev = node;head.next = node;node.prev = head;}//移除节点private void removeNode(Node node){node.prev.next = node.next;node.next.prev = node.prev;}private static void printCache(Node head){Node current = head;while (current != null){System.out.print("(" + current.key + ", " + current.value + ") -> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {LRUCache lruCache = new LRUCache(3);// 插入键值对 (1, "A")lruCache.put(1, "A");// 插入键值对 (2, "B")lruCache.put(2, "B");// 插入键值对 (3, "C")lruCache.put(3, "C");// 此时缓存状态为:3 -> 2 -> 1,其中1是最近访问的,3是最久未使用的System.out.println("初始缓存状态为:");printCache(lruCache.head);// 获取键1对应的值,输出"A"System.out.println(" // 获取键1对应的值:"+lruCache.get(1));// 此时缓存状态不变:1 -> 3 -> 2System.out.println("获取键1对应的值,输出\"A\"后的缓存状态为:");printCache(lruCache.head);// 插入键值对 (4, "D"),此时缓存已满,需要逐出最久未使用的键值对,即键2 -> 值B被逐出lruCache.put(4, "D");// 此时缓存状态为:4 -> 1 -> 3,其中3是最久未使用的,4是最近访问的System.out.println("插入键值对 (4, \"D\"),此时缓存已满,需要逐出最久未使用的键值对,即键2 -> 值B被逐出的缓存状态为:");printCache(lruCache.head);// 获取键2对应的值,由于键2已经被逐出,输出-1System.out.println("获取键2对应的值:"+lruCache.get(2));// 此时缓存状态不变:4 -> 1 -> 3System.out.println("获取键2对应的值,由于键2已经被逐出,输出-1的缓存状态为:");printCache(lruCache.head);// 插入键值对 (5, "E"),此时缓存已满,需要逐出最久未使用的键值对,即键3 -> 值C被逐出lruCache.put(5, "E");// 此时缓存状态为:5 -> 4 -> 1,其中1是最久未使用的,5是最近访问的System.out.println("插入键值对 (5, \"E\"),此时缓存已满,需要逐出最久未使用的键值对,即键3 -> 值C被逐出的缓存状态为:");printCache(lruCache.head);// 获取键3对应的值,由于键3已经被逐出,输出-1System.out.println("获取键3对应的值:"+lruCache.get(3));// 此时缓存状态不变:5 -> 4 -> 1System.out.println(" // 获取键3对应的值,由于键3已经被逐出,输出-1的缓存状态为:");printCache(lruCache.head);}
}相关文章:
Java算法_ LRU 缓存(LeetCode_Hot100)
题目描述:请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 获得更多?算法思路:代码文档,算法解析的私得。 运行效果 完整代码 import java.util.HashMap; import java.util.Map;/*** 2 * Author: L…...
Hugging Face 的文本生成和大语言模型的开源生态
[更新于 2023 年 7 月 23 日: 添加 Llama 2。] 文本生成和对话技术已经出现多年了。早期的挑战在于通过设置参数和分辨偏差,同时控制好文本忠实性和多样性。更忠实的输出一般更缺少创造性,并且和原始训练数据更加接近,也更不像人话。最近的研…...
Docker Compose用法详解
文章目录 Docker Compose是什么安装Docker ComposeCompose文件编写使用Docker Compose部署-管理应用 Docker Compose是什么 Docker Compose是一个用于定义和运行多容器Docker应用程序的python工具。它允许您使用一个单独的配置文件来定义和配置多个相关容器的服务,…...
分布式链路追踪概述
分布式链路追踪概述 文章目录 分布式链路追踪概述1.分布式链路追踪概述1.1.什么是 Tracing1.2.为什么需要Distributed Tracing 2.Google Dapper2.1.Dapper的分布式跟踪2.1.1.跟踪树和span2.1.2.Annotation2.1.3.采样率 3.OpenTracing3.1.发展历史3.2.数据模型 4.java探针技术-j…...
css中的var函数
css中的var函数 假设我们在css文件存在多个相同颜色值,当css文件越来越大的时候,想要改颜色就要手动在每个旧颜色上修改,这样维护工作非常难进行。 但是我们可以使用变量来存储值,这样可以在整个css样式表中重复使用,…...
第五次作业 运维高级 构建 LVS-DR 集群和配置nginx负载均衡
1、基于 CentOS 7 构建 LVS-DR 群集。 LVS-DR模式工作原理 首先,来自客户端计算机CIP的请求被发送到Director的VIP。然后Director使用相同的VIP目的IP地址将请求发送到集群节点或真实服务器。然后,集群某个节点将回复该数据包,并将该数据包…...
neo4j电影库-关系查询
关系类型数量源数据目标数据属性ACTED_IN172演员电影roles(角色扮演)属性,属性值为数组DIRECTED44导演电影无PRODUCED15制片商电影无WROTE10作家电影无FOLLOWS3影评人影评人无REVIEWED9影评人电影summary(影评摘要)和 …...
2020/10-2023/7 Notes
2020/10-2023/7 Notes 1.Unity WebGL 字体 动态字体 2.Path.Combine 3.播放Unity WebGL构建包 Vistual Studio Code->Extensions->Live Server 4.Cloud Compare laszip.net RenderDoc Mike Zero Ras Mapper HDF Viewer 5.使Unity支持GLSL Project->添加命令行参数-&g…...
在UOS系统中管理ORACLE数据库
在明确了“数字中国”建设战略后。自主创新与国产化已成为我国实现科技强国、经济强国的发展趋势与行业共识。 即信息技术应用创新产业,简称“信创”。 而现有的国产操作系统,虽然已日趋成熟,但因为很多应用软件由国外垄断,因此…...
以http_proxy和ajp_proxy方式整合apache和tomcat(动静分离)
注意:http_proxy和ajp_proxy的稳定性不如mod_jk 一.http_proxy方式 1.下载mod_proxy_html.x86_64 2.在apache下创建http_proxy.conf文件(或者直接写到conf/httpd.conf文件最后) 3.查看server.xml文件 到tomcat的安装目录下的conf/serve…...
【pinia】Pinia入门和基本使用:
文章目录 一、 什么是pinia二、 创建空Vue项目并安装Pinia1. 创建空Vue项目2. 安装Pinia并注册 三、 实现counter四、 实现getters五、 异步action六、 storeToRefs保持响应式解构七、基本使用:【1】main.js【2】store》index.js【3】member.ts 一、 什么是pinia P…...
Linux 文件系统(一)系统目录
系统目录 基本概念分区划分目录划分 基本概念 虽然Linux有很多不同的发行版,但是其基本目录结构都是类似的,因此只要了解一个发行版基本足矣。 分区划分 系统默认 大致有以下几种分区 /(根目录):该分区包含了操作系…...
『CV学习笔记』Opencv和PIL Image以及base64编码互相转化
Opencv和PIL Image以及base64编码互相转化 文章目录 一. opencv&PIL.Image&Skimage1.1. opencv-python读取透明图片(带alpha通道)1.2. opencv、PIL.Image、Skimage读取的彩色图片维度区别1.3. opencv、PIL.Image转换二. base64和cv2 imge互相转换三. base64和PIL imge互…...
行业追踪,2023-08-07
自动复盘 2023-08-07 凡所有相,皆是虚妄。若见诸相非相,即见如来。 k 线图是最好的老师,每天持续发布板块的rps排名,追踪板块,板块来开仓,板块去清仓,丢弃自以为是的想法,板块去留让…...
CSRF 攻击和 XSS 攻击分别代表什么?如何防范?
一:PHP 1. CSRF 攻击和 XSS 攻击分别代表什么? 1.CSRF攻击 1.概念: CSRF(Cross-site request forgery)跨站请求伪造,用户通过跨站请求,以合法身份做非法的事情 2.原理: 1.登录受信任…...
RabbitMQ: 详解、使用教程和示例
RabbitMQ: 详解、使用教程和示例 什么是 RabbitMQ? RabbitMQ 是一个开源的消息代理(Message Broker)软件,它实现了高级消息队列协议(AMQP),用于在应用程序之间进行异步消息传递。它允许应用程…...
redis NOAUTH Authentication required 可能不是密码问题
开发环境 springboot 2.4.3 spring-boot-starter-data-redis 2.4.3 redis 4.0 lettuce 6.0.2 背景 多环境(test,pre,prd)部署,在测试环境测试通过之后部署预发环境的时候,服务一直报错,提示【i…...
动态规划解0-1背包问题(超详细理解)
前言: 好久没写0-1背包问题了,都有些不记得了,写这篇文章给自己以后做简单参考,如果能同时帮到读者,不胜荣幸。 正文 0-1背包问题是这样的一个问题,假设有一个背包,其容量为 capacity 。在地…...
有哪些可能引起前端安全的问题?
跨站脚本 (Cross-Site Scripting, XSS) ⼀种代码注⼊⽅式,为了与 CSS 区分所以被称作 XSS。早期常⻅于⽹络论坛, 起因是⽹站没有对⽤户的输⼊进⾏严格的限制, 使得攻击者可以将脚本上传到帖⼦让其他⼈浏览到有恶意脚本的⻚⾯, 其注⼊⽅式很简单包括但不限于 JavaScript / CSS …...
【Unity实战100例】用户头像圆形遮罩使用Shader不用Mask组件
目录 一.创建材质 二.创建Shader文件编写Shader代码 三.Image材质设置 源码:https://download.csdn.net/download/qq_37310110/88196529 前言:我们在使用Unity的自带组件Mask的时候会出现毛边现象很难处理掉,这里我们使用着色器shader来进行处理就不会出现毛边现象。...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
