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

LRU自定义最近最少使用-java实现

LRU自定义最近最少使用

  • 一:leetCode 题目
  • 二:思路
  • 三:上代码
    • 3.1:类代码
    • 3.2: 测试代码

一:leetCode 题目

题目链接:

题目链接:146.LRU缓存

为什么要写博客记录下呢?

1.这个题很锻炼自己的编码能力(代码量多,结构多)
2.这个题很锻炼自己的owner能力(感觉挑战底层类,不屈于写业务代码)
3.这个题很锻炼自己的耐力(调试比较麻烦)
4.这个题很锻炼自己的边界能力(各种边界条件需要测试)

二:思路

  1. 最近最少使用:

最近最少使用 翻译下:把最后一个不使用的给踢出去

维护一个队列
使用的放到队列的前头
队尾永远是最近最少使用的

翻译:使用了就放队列前头,想移除就移除队尾

  1. 如何实现队列,O(1) 的复杂度

首先想到的是链表,这里使用最普通的 listNode的结构体

class ListNode {int val;ListNode next;ListNode parent;public ListNode(int val) {this.val = val;this.next = null;this.parent = null;}
}

三:上代码

代码:

  • 类代码
  • 测试代码

3.1:类代码

import java.util.HashMap;
import java.util.Map;public class LRUCache {// 初始化的容量private final int capacity;// 元数据private final Map<Integer, Integer> metaMap;// 用于记录 key 和队列的关系private final Map<Integer, ListNode> metaLinkedMap;// 最后一个结点private ListNode lastNode;// 头结点private final ListNode headNode;public LRUCache(int capacity) {this.capacity = capacity;metaMap = new HashMap<>();metaLinkedMap = new HashMap<>();// 请注意!!! 这里我太笨了,我这里前两个结点都是头结点。这样有利于我个人的思考 !!!!!ListNode dataNode = new ListNode(0);headNode = new ListNode(0);headNode.next = dataNode;}// 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1public int get(int key) {if (metaMap.containsKey(key)) {// 调整频率adjustExistNodeSort(key);return metaMap.get(key);}return -1;}// 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字public void put(int key, int value) {if (metaMap.containsKey(key)) {// 更新热点数据adjustExistNodeSort(key);// 替换数据metaMap.put(key, value);} else {if (metaMap.size() == capacity) {// 需要移除数据removeLastNode();}ListNode putNode = new ListNode(key);// 更新热点数据adjustNewNodeSort(putNode);// 初始化信息metaMap.put(key, value);metaLinkedMap.put(key, putNode);}}/*** 排序一个已经存在的结点* @param key 已经存在的key*/private void adjustExistNodeSort(Integer key) {ListNode hotNode = metaLinkedMap.get(key);ListNode oldHeadNode = headNode.next.next;if (hotNode == oldHeadNode){return;}hotNode.parent.next = hotNode.next;if (hotNode.next != null){hotNode.next.parent = hotNode.parent;}if (lastNode == hotNode && metaMap.size() != 1) {lastNode = hotNode.parent;}if (oldHeadNode != null) {oldHeadNode.parent = hotNode;hotNode.next = oldHeadNode;}headNode.next.next = hotNode;hotNode.parent = headNode.next;}/*** 调整一个新结点的排序* @param putNode 新节点*/private void adjustNewNodeSort(ListNode putNode) {// 初始化末尾节点if (lastNode == null || metaMap.size() == 0) {lastNode = putNode;}// 放到头节点ListNode oldHeadNode = headNode.next.next;if (oldHeadNode != null) {oldHeadNode.parent = putNode;putNode.next = oldHeadNode;}headNode.next.next = putNode;putNode.parent = headNode.next;}/*** 移除最后一个元素*/private void removeLastNode() {int lastVal = lastNode.val;metaMap.remove(lastVal);metaLinkedMap.remove(lastVal);lastNode = lastNode.parent;lastNode.next = null;}
}class ListNode {int val;ListNode next;ListNode parent;public ListNode(int val) {this.val = val;this.next = null;this.parent = null;}
}

3.2: 测试代码

import java.util.HashSet;
import java.util.Set;// Press Shift twice to open the Search Everywhere dialog and type `show whitespaces`,
// then press Enter. You can now see whitespace characters in your code.
public class Main {public static void main(String[] args) {LRUCache lruCache = new LRUCache(1);lruCache.get(6);lruCache.get(8);lruCache.put(12,1);lruCache.get(2);lruCache.put(15,11);lruCache.put(5,2);lruCache.put(1,15);lruCache.put(4,2);lruCache.get(5);lruCache.put(15,15);}
}

相关文章:

LRU自定义最近最少使用-java实现

LRU自定义最近最少使用 一&#xff1a;leetCode 题目二&#xff1a;思路三&#xff1a;上代码3.1&#xff1a;类代码3.2&#xff1a; 测试代码 一&#xff1a;leetCode 题目 题目链接&#xff1a; 题目链接&#xff1a;146.LRU缓存 为什么要写博客记录下呢&#xff1f; 1.这个…...

spring:详解spring boot

spring的优缺点 虽然Spring的组件代码是轻量级的&#xff0c;但它的配置却是重量级的。一开始&#xff0c;Spring用XML配置&#xff0c;而且是很多XML配 置。Spring 2.5引入了基于注解的组件扫描&#xff0c;这消除了大量针对应用程序自身组件的显式XML配置。Spring 3.0引入 了…...

大数据Doris(八):启动FE步骤

文章目录 启动FE步骤 一、配置环境变量 二、​​​​​​​创建doris-mate...

vuex常用属性

以下是Vuex常用属性&#xff1a; state&#xff1a;存储应用程序状态的数据 getters&#xff1a;获取应用程序状态的计算属性 mutations&#xff1a;修改应用程序状态的同步方法 actions&#xff1a;修改应用程序状态的异步方法 modules&#xff1a;将应用程序状态分为模块…...

M-LVDS收发器MS2111可pin对pin兼容SN65MLVD206

MS2111 是多点低压差分(M-LVDS)线路驱动器和接收器&#xff0c;经过优化可在高达 200 Mbps 的信令速率下运行。可pin对pin兼容SN65MLVD206。所有部件均符合 M-LVDS 标准 TIA / EIA-899。该驱动器输出已设计为支持负载低至 30Ω 的多点总线。 MS2111 的接收器属于 Type-2, 它们可…...

JVM-Java字节码的组成部分

Java字节码文件是一种由Java编译器生成的二进制文件&#xff0c;用于在Java虚拟机&#xff08;JVM&#xff09;上执行Java程序。字节码文件的组成可以分为以下几个主要部分&#xff1a; 基本信息&#xff1a; 魔数&#xff08;Magic Number&#xff09;&#xff1a;前4个字节的…...

C# 图像灰化处理方法及速度对比

图像处理过程中&#xff0c;比较常见的灰化处理&#xff0c;将彩色图像处理为黑白图像&#xff0c;以便后续的其他处理工作。 在面对大量的图片或者像素尺寸比较大的图片的时候&#xff0c;处理速度和性能就显得非常重要&#xff0c;下面分别用3种方式来处理图像数据&#xff0…...

【嵌入式】STM32F031K4U6、STM32F031K6U6、STM32F031K6T6主流ARM Cortex-M0基本型系列MCU规格参数

一、电路原理图 【嵌入式】STM32F031K4U6、STM32F031K6U6、STM32F031K6T6主流ARM Cortex-M0基本型系列MCU —— 明佳达 二、规格参数 1、STM32F031K4U6&#xff08;16KB&#xff09;闪存 32UFQFPN 核心处理器&#xff1a;ARM Cortex-M0 内核规格&#xff1a;32 位单核 速度&a…...

04_学习springdoc与oauth结合_简述

文章目录 1 前言2 基本结构3 需要做的配置 简述4 需要做的配置 详述4.1 backend-api-gateway 的配置4.1.1 application.yml 4.2 backend-film 的配置4.2.1 pom.xml 引入依赖4.2.2 application.yml 的配置4.2.3 Spring Security 资源服务器的配置类 MyResourceServerConfig4.2.4…...

【设计模式】单例模式的7种实现方法

一、饿汉式-线程安全 线程安全&#xff0c;但无法实现实例懒加载策略 /*** 饿汉式* author CC* version 1.0* since2023/10/12*/ public class Singleton {private static final Singleton singleton new Singleton();private Singleton() {}public static Singleton getSin…...

AlphaPose Pytorch 代码详解(一):predict

前言 代码地址&#xff1a;AlphaPose-Pytorch版 本文以图像 1.jpg&#xff08;854x480&#xff09;为例对整个预测过程的各个细节进行解读并记录 python demo.py --indir examples/demo --outdir examples/res --save_img1. YOLO 1.1 图像预处理 cv2读取BGR图像 img [480,…...

日常学习记录随笔-zabix实战

使用zabix结合 实现一套监控报警装置 不管是web开发还是大数据开发 我们的离线项目还是实时项目也好&#xff0c;都需要把我们的应用提交到我们服务器或者容器中去执行 整个应用过程中怎么保证线上整体环境的稳定运行 监控很重要 现在比较主流的就是 普罗米修斯以及zabix 我要做…...

vw+rem自适应布局

开发过程中&#xff0c;我们希望能够直接按照设计图来开发&#xff0c;不管设计图是两倍还是三倍图&#xff0c;能够直接写设计图尺寸而不需要换算&#xff0c;同时有高质的设计图还原度&#xff0c;想想都比较爽。 这里介绍一种使用vw和rem来布局的方案。 该方案思路主要是&am…...

【MySql】mysql之MHA高可用配置及故障切换

一、MHA概念 MHA&#xff08;Master High Availability&#xff09;是一套优秀的Mysql高可用环境下故障切换和主从复制的软件。 MHA的出现就是解决Mysql单点的问题。 Mysql故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过程中最大程…...

如何在 Spring Boot 中进行数据备份

在Spring Boot中进行数据备份 数据备份是确保数据安全性和可恢复性的关键任务之一。Spring Boot提供了多种方法来执行数据备份&#xff0c;无论是定期备份数据库&#xff0c;还是将数据导出到外部存储。本文将介绍在Spring Boot应用程序中进行数据备份的不同方法。 方法1: 使用…...

为Yolov7环境安装Cuba匹配的Pytorch

1. 查看Cuba版本 方法一 nvidia-smi 找到CUDA Version 方法二 Nvidia Control Panel > 系统信息 > 组件 > 2. 安装Cuba匹配版本的PyTorch https://pytorch.org/get-started/locally/这里使用conda安装 conda install pytorch torchvision torchaudio pytorch-cu…...

SpringBoot基于jackson对象映射器扩展mvc框架的消息转换器

在SpringBoot中&#xff0c;可以基于jackson对象映射器扩展mvc框架的消息转换器 具体步骤如下&#xff1a; 1、创建对象映射器&#xff1a; package com.java.demo.common;import com.fasterxml.jackson.databind.DeserializationFeature; import com.fasterxml.jackson.datab…...

计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度(matlab代码)

目录 1 主要内容 系统结构 CCPP-P2G-燃气机组子系统 非线性处理缺陷 2 部分代码 3 程序结果 4 程序链接 1 主要内容 该程序参考《计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度》模型&#xff0c;主要实现的是计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度…...

【低代码表单设计器】:创造高效率的流程化办公!

当前&#xff0c;有不少用户朋友对低代码表单设计器挺感兴趣。其实&#xff0c;如果想要实现提质增效的办公效率&#xff0c;创造一个流程化办公&#xff0c;那么确实可以了解低代码技术平台。流辰信息作为服务商&#xff0c;拥有较强的自主研发能力&#xff0c;根据市场的变化…...

26、类型别名

类型别名 顾名思义&#xff0c;其实就是类型类型起别名&#xff08;新起一个名字&#xff09; demo&#xff1a; type Name string; type NameConsole () > string; type NameUnite Name | NameConsole; function getName(n: NameUnite): Name {if( typeof n string)…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

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

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

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...