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

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...