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

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)

题目描述&#xff1a;请你设计并实现一个满足 LRU &#xff08;最近最少使用&#xff09; 缓存 约束的数据结构。 获得更多&#xff1f;算法思路:代码文档&#xff0c;算法解析的私得。 运行效果 完整代码 import java.util.HashMap; import java.util.Map;/*** 2 * Author: L…...

Hugging Face 的文本生成和大语言模型的开源生态

[更新于 2023 年 7 月 23 日: 添加 Llama 2。] 文本生成和对话技术已经出现多年了。早期的挑战在于通过设置参数和分辨偏差&#xff0c;同时控制好文本忠实性和多样性。更忠实的输出一般更缺少创造性&#xff0c;并且和原始训练数据更加接近&#xff0c;也更不像人话。最近的研…...

Docker Compose用法详解

文章目录 Docker Compose是什么安装Docker ComposeCompose文件编写使用Docker Compose部署-管理应用 Docker Compose是什么 Docker Compose是一个用于定义和运行多容器Docker应用程序的python工具。它允许您使用一个单独的配置文件来定义和配置多个相关容器的服务&#xff0c;…...

分布式链路追踪概述

分布式链路追踪概述 文章目录 分布式链路追踪概述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文件存在多个相同颜色值&#xff0c;当css文件越来越大的时候&#xff0c;想要改颜色就要手动在每个旧颜色上修改&#xff0c;这样维护工作非常难进行。 但是我们可以使用变量来存储值&#xff0c;这样可以在整个css样式表中重复使用&#xff0c…...

第五次作业 运维高级 构建 LVS-DR 集群和配置nginx负载均衡

1、基于 CentOS 7 构建 LVS-DR 群集。 LVS-DR模式工作原理 首先&#xff0c;来自客户端计算机CIP的请求被发送到Director的VIP。然后Director使用相同的VIP目的IP地址将请求发送到集群节点或真实服务器。然后&#xff0c;集群某个节点将回复该数据包&#xff0c;并将该数据包…...

neo4j电影库-关系查询

关系类型数量源数据目标数据属性ACTED_IN172演员电影roles&#xff08;角色扮演&#xff09;属性&#xff0c;属性值为数组DIRECTED44导演电影无PRODUCED15制片商电影无WROTE10作家电影无FOLLOWS3影评人影评人无REVIEWED9影评人电影summary&#xff08;影评摘要&#xff09;和 …...

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数据库

在明确了“数字中国”建设战略后。自主创新与国产化已成为我国实现科技强国、经济强国的发展趋势与行业共识。 即信息技术应用创新产业&#xff0c;简称“信创”。 而现有的国产操作系统&#xff0c;虽然已日趋成熟&#xff0c;但因为很多应用软件由国外垄断&#xff0c;因此…...

以http_proxy和ajp_proxy方式整合apache和tomcat(动静分离)

注意&#xff1a;http_proxy和ajp_proxy的稳定性不如mod_jk 一.http_proxy方式 1.下载mod_proxy_html.x86_64 2.在apache下创建http_proxy.conf文件&#xff08;或者直接写到conf/httpd.conf文件最后&#xff09; 3.查看server.xml文件 到tomcat的安装目录下的conf/serve…...

【pinia】Pinia入门和基本使用:

文章目录 一、 什么是pinia二、 创建空Vue项目并安装Pinia1. 创建空Vue项目2. 安装Pinia并注册 三、 实现counter四、 实现getters五、 异步action六、 storeToRefs保持响应式解构七、基本使用&#xff1a;【1】main.js【2】store》index.js【3】member.ts 一、 什么是pinia P…...

Linux 文件系统(一)系统目录

系统目录 基本概念分区划分目录划分 基本概念 虽然Linux有很多不同的发行版&#xff0c;但是其基本目录结构都是类似的&#xff0c;因此只要了解一个发行版基本足矣。 分区划分 系统默认 大致有以下几种分区 /&#xff08;根目录&#xff09;&#xff1a;该分区包含了操作系…...

『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 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…...

CSRF 攻击和 XSS 攻击分别代表什么?如何防范?

一&#xff1a;PHP 1. CSRF 攻击和 XSS 攻击分别代表什么&#xff1f; 1.CSRF攻击 1.概念&#xff1a; CSRF&#xff08;Cross-site request forgery&#xff09;跨站请求伪造&#xff0c;用户通过跨站请求&#xff0c;以合法身份做非法的事情 2.原理&#xff1a; 1.登录受信任…...

RabbitMQ: 详解、使用教程和示例

RabbitMQ: 详解、使用教程和示例 什么是 RabbitMQ&#xff1f; RabbitMQ 是一个开源的消息代理&#xff08;Message Broker&#xff09;软件&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;&#xff0c;用于在应用程序之间进行异步消息传递。它允许应用程…...

redis NOAUTH Authentication required 可能不是密码问题

开发环境 springboot 2.4.3 spring-boot-starter-data-redis 2.4.3 redis 4.0 lettuce 6.0.2 背景 多环境&#xff08;test&#xff0c;pre&#xff0c;prd&#xff09;部署&#xff0c;在测试环境测试通过之后部署预发环境的时候&#xff0c;服务一直报错&#xff0c;提示【i…...

动态规划解0-1背包问题(超详细理解)

前言&#xff1a; 好久没写0-1背包问题了&#xff0c;都有些不记得了&#xff0c;写这篇文章给自己以后做简单参考&#xff0c;如果能同时帮到读者&#xff0c;不胜荣幸。 正文 0-1背包问题是这样的一个问题&#xff0c;假设有一个背包&#xff0c;其容量为 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来进行处理就不会出现毛边现象。...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

Linux 中如何提取压缩文件 ?

Linux 是一种流行的开源操作系统&#xff0c;它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间&#xff0c;使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的&#xff0c;要在 …...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...