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);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/84361.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Effective Java笔记(26)请不要使用原生态类型

首先介绍一些术语 。 声明中具有一个或者多个类型参数&#xff08; type parameter &#xff09;的类或者接口&#xff0c;就是泛型&#xff08; generic &#xff09;类或者接口 。 例如&#xff0c;List 接口就只有单个类型参数 E &#xff0c;表示列表的元素类型 。这个接口…

竞赛项目 深度学习的视频多目标跟踪实现

文章目录 1 前言2 先上成果3 多目标跟踪的两种方法3.1 方法13.2 方法2 4 Tracking By Detecting的跟踪过程4.1 存在的问题4.2 基于轨迹预测的跟踪方式 5 训练代码6 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的视频多目标跟踪实现 …

freeswitch的mod_xml_curl模块动态获取dialplan

概述 freeswitch是一款简单好用的VOIP开源软交换平台。 mod_xml_curl模块支持从web服务获取xml配置&#xff0c;本文介绍如何动态获取dialplan配置。 环境 centos&#xff1a;CentOS release 7.0 (Final)或以上版本 freeswitch&#xff1a;v1.6.20 GCC&#xff1a;4.8.5…

【HarmonyOS】Java如何引用外部jar包

【关键字】 Java、引用jar包​ 【写在前面】 使用API6和API7开发HarmonyOS应用时&#xff0c;因为应用中只能引用SDK中开放的功能接口&#xff0c;但是部分jdk自带的接口功能在SDK中并未封装&#xff0c;要想在工程中使用jdk开放的接口功能&#xff0c;需要将jdk中的jar包通过…

科技资讯|苹果手机版Vision Pro头显专利曝光,内嵌苹果手机使用

根据美国商标和专利局&#xff08;USPTO&#xff09;公示的清单&#xff0c;苹果公司近日获得了一项头显相关的技术专利&#xff0c;展示了一款亲民款 Vision Pro 头显&#xff0c;可以将 iPhone 放置在头显内部充当屏幕。 根据patentlyapple 媒体报道&#xff0c;这是苹果公司…

1.RuoYi-Vue前后端分离版本启动

1.代码下载 去若依官网&#xff0c;选择RuoYI前后端分离版: 下载地址&#xff1a;https://gitee.com/y_project/RuoYi-Vue 2.依赖环境的部署 1.Mysql 2.Redis安装部署 : https://blog.csdn.net/qq_27860623/article/details/132168382 3.Idea打开后端服务 用Idea打开后端的…

计算机服务器被360后缀勒索病毒攻击怎么办,勒索病毒解密

计算机技术的不断发展&#xff0c;不仅方便了企业的生产生活&#xff0c;也为社会的发展带来了巨大贡献&#xff0c;但随之而来的网络威胁也不断增加&#xff0c;勒索病毒就是其中较为常见的常见的威胁。近期&#xff0c;我们收到很多企业的求助&#xff0c;企业的计算机服务器…

Qt应用开发(基础篇)——堆栈窗口 QStackedWidget

一、前言 QStackedWidget继承于QFrame&#xff0c;QFrame继承于QWidget&#xff0c;是Qt常用的堆栈窗口部件。 框架类QFrame介绍 QStackedWidget堆栈窗口&#xff0c;根据下标切换&#xff0c;一次显示一个小部件&#xff0c;常用于应用界面切换、图片轮询播放等场景。 二、QSt…

Unity-Shader-高亮Highlight

常用Shader-高亮&#xff0c;可动态调整高亮颜色、高亮强度范围/等级、高亮闪烁速度、高亮状态 Shader "CustomShader/Highlight" {Properties{_Color("Color", Color) (0.9044118,0.6640914,0.03325041,0)_Albedo("Albedo", 2D) "white…

Stable Diffusion - Candy Land (糖果世界) LoRA 提示词配置与效果展示

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/132145248 糖果世界 (Candy Land) 是一个充满甜蜜和奇幻的地方&#xff0c;由各种各样的糖果和巧克力构成。在糖果世界&#xff0c;可以看到&…

全网最细,Fiddler修改接口返回数据详细步骤实战,辅助接口测试...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 在测试的过程中&a…

年之年的选择,组装版

组件&#xff1a;<!--* Author: liuyu liuyuxizhengtech.com* Date: 2023-02-01 16:57:27* LastEditors: wangping wangpingxizhengtech.com* LastEditTime: 2023-06-30 17:25:14* Description: 时间选择年 - 年 --> <template><div class"year-range-pick…

Nacos服务治理—负载均衡

引入负载均衡 在消费方引入负载均衡机制&#xff0c;同时简化获取服务提供者信息的流程 Spring Cloud引入组件LoadBalance实现负载均衡 添加依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web<…

MyBatis-动态SQL-foreach

目录 标签有以下常用属性&#xff1a; 小结 <froeach> <foreach>标签有以下常用属性&#xff1a; collection&#xff1a;指定要迭代的集合或数组的参数名&#xff08;遍历的对象&#xff09;。item&#xff1a;指定在迭代过程中的每个元素的别名&#xff08;遍历…

【python 深度学习】解决遇到的问题

目录 一、RuntimeError: module compiled against API version 0xc but this version of numpy is 0xb 二、AttributeError: module ‘tensorflow’ has no attribute ‘flags’ 三、conda 更新 Please update conda by running 四、to search for alternate channels that…

【Spring专题】手写简易Spring容器过程分析

前置知识 《【Spring专题】Spring底层核心原理解析》 思路整理 我们在上一节《【Spring专题】Spring底层核心原理解析》课里面有简单分析过一个Spring容器的一般流程&#xff0c;所以&#xff0c;本节课我们这里尝试写一下简易的Spring容器。 手写源码示例 一、手写前的准…

[足式机器人]Part4 机械设计 Ch00/01 绪论+机器结构组成与连接 ——【课程笔记】

本文仅供学习使用 本文参考&#xff1a; 《机械设计》 王德伦 马雅丽课件与日常作业可登录网址 http://edu.bell-lab.com/manage/#/login&#xff0c;选择观摩登录&#xff0c;查看2023机械设计2。 机械设计-Ch00Ch01——绪论机器结构组成与连接 Ch00-绪论0.1 何为机械设计——…

python爬虫实战(1)--爬取新闻数据

想要每天看到新闻数据又不想占用太多时间去整理&#xff0c;萌生自己抓取新闻网站的想法。 1. 准备工作 使用python语言可以快速实现&#xff0c;调用BeautifulSoup包里面的方法 安装BeautifulSoup pip install BeautifulSoup完成以后引入项目 2. 开发 定义请求头&#xf…

Servlet介绍

1.简介 Servlet是JavaWeb最为核心的内容&#xff0c;它是Java提供的一门动态web资源开发技术。 使用Servlet就可以实现&#xff0c;根据不同的登录用户在页面上动态显示不同内容。 Servlet是JavaEE规范之一&#xff0c;其实就是一个接口&#xff0c;将来我们需要定义Servlet类…

【果树农药喷洒机器人】Part3:变量喷药系统工作原理介绍

本专栏介绍&#xff1a;免费专栏&#xff0c;持续更新机器人实战项目&#xff0c;欢迎各位订阅关注。 关注我&#xff0c;带你了解更多关于机器人、嵌入式、人工智能等方面的优质文章&#xff01; 文章目录 一、变量喷药系统工作原理二、液压通路设计与控制系统封装2.1液压通路…