当前位置: 首页 > 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)…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...