当前位置: 首页 > 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来进行处理就不会出现毛边现象。...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...