LRU自定义最近最少使用-java实现
LRU自定义最近最少使用
- 一:leetCode 题目
- 二:思路
- 三:上代码
- 3.1:类代码
- 3.2: 测试代码
一:leetCode 题目
题目链接:
题目链接:146.LRU缓存
为什么要写博客记录下呢?
1.这个题很锻炼自己的编码能力(代码量多,结构多)
2.这个题很锻炼自己的owner能力(感觉挑战底层类,不屈于写业务代码)
3.这个题很锻炼自己的耐力(调试比较麻烦)
4.这个题很锻炼自己的边界能力(各种边界条件需要测试)
二:思路
- 最近最少使用:
最近最少使用 翻译下:把最后一个不使用的给踢出去
维护一个队列
使用的放到队列的前头
队尾永远是最近最少使用的翻译:使用了就放队列前头,想移除就移除队尾
- 如何实现队列,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自定义最近最少使用 一:leetCode 题目二:思路三:上代码3.1:类代码3.2: 测试代码 一:leetCode 题目 题目链接: 题目链接:146.LRU缓存 为什么要写博客记录下呢? 1.这个…...
spring:详解spring boot
spring的优缺点 虽然Spring的组件代码是轻量级的,但它的配置却是重量级的。一开始,Spring用XML配置,而且是很多XML配 置。Spring 2.5引入了基于注解的组件扫描,这消除了大量针对应用程序自身组件的显式XML配置。Spring 3.0引入 了…...
大数据Doris(八):启动FE步骤
文章目录 启动FE步骤 一、配置环境变量 二、创建doris-mate...
vuex常用属性
以下是Vuex常用属性: state:存储应用程序状态的数据 getters:获取应用程序状态的计算属性 mutations:修改应用程序状态的同步方法 actions:修改应用程序状态的异步方法 modules:将应用程序状态分为模块…...
M-LVDS收发器MS2111可pin对pin兼容SN65MLVD206
MS2111 是多点低压差分(M-LVDS)线路驱动器和接收器,经过优化可在高达 200 Mbps 的信令速率下运行。可pin对pin兼容SN65MLVD206。所有部件均符合 M-LVDS 标准 TIA / EIA-899。该驱动器输出已设计为支持负载低至 30Ω 的多点总线。 MS2111 的接收器属于 Type-2, 它们可…...
JVM-Java字节码的组成部分
Java字节码文件是一种由Java编译器生成的二进制文件,用于在Java虚拟机(JVM)上执行Java程序。字节码文件的组成可以分为以下几个主要部分: 基本信息: 魔数(Magic Number):前4个字节的…...
C# 图像灰化处理方法及速度对比
图像处理过程中,比较常见的灰化处理,将彩色图像处理为黑白图像,以便后续的其他处理工作。 在面对大量的图片或者像素尺寸比较大的图片的时候,处理速度和性能就显得非常重要,下面分别用3种方式来处理图像数据࿰…...
【嵌入式】STM32F031K4U6、STM32F031K6U6、STM32F031K6T6主流ARM Cortex-M0基本型系列MCU规格参数
一、电路原理图 【嵌入式】STM32F031K4U6、STM32F031K6U6、STM32F031K6T6主流ARM Cortex-M0基本型系列MCU —— 明佳达 二、规格参数 1、STM32F031K4U6(16KB)闪存 32UFQFPN 核心处理器:ARM Cortex-M0 内核规格: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种实现方法
一、饿汉式-线程安全 线程安全,但无法实现实例懒加载策略 /*** 饿汉式* 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
前言 代码地址:AlphaPose-Pytorch版 本文以图像 1.jpg(854x480)为例对整个预测过程的各个细节进行解读并记录 python demo.py --indir examples/demo --outdir examples/res --save_img1. YOLO 1.1 图像预处理 cv2读取BGR图像 img [480,…...
日常学习记录随笔-zabix实战
使用zabix结合 实现一套监控报警装置 不管是web开发还是大数据开发 我们的离线项目还是实时项目也好,都需要把我们的应用提交到我们服务器或者容器中去执行 整个应用过程中怎么保证线上整体环境的稳定运行 监控很重要 现在比较主流的就是 普罗米修斯以及zabix 我要做…...
vw+rem自适应布局
开发过程中,我们希望能够直接按照设计图来开发,不管设计图是两倍还是三倍图,能够直接写设计图尺寸而不需要换算,同时有高质的设计图还原度,想想都比较爽。 这里介绍一种使用vw和rem来布局的方案。 该方案思路主要是&am…...
【MySql】mysql之MHA高可用配置及故障切换
一、MHA概念 MHA(Master High Availability)是一套优秀的Mysql高可用环境下故障切换和主从复制的软件。 MHA的出现就是解决Mysql单点的问题。 Mysql故障切换过程中,MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的过程中最大程…...
如何在 Spring Boot 中进行数据备份
在Spring Boot中进行数据备份 数据备份是确保数据安全性和可恢复性的关键任务之一。Spring Boot提供了多种方法来执行数据备份,无论是定期备份数据库,还是将数据导出到外部存储。本文将介绍在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中,可以基于jackson对象映射器扩展mvc框架的消息转换器 具体步骤如下: 1、创建对象映射器: package com.java.demo.common;import com.fasterxml.jackson.databind.DeserializationFeature; import com.fasterxml.jackson.datab…...
计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度(matlab代码)
目录 1 主要内容 系统结构 CCPP-P2G-燃气机组子系统 非线性处理缺陷 2 部分代码 3 程序结果 4 程序链接 1 主要内容 该程序参考《计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度》模型,主要实现的是计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度…...
【低代码表单设计器】:创造高效率的流程化办公!
当前,有不少用户朋友对低代码表单设计器挺感兴趣。其实,如果想要实现提质增效的办公效率,创造一个流程化办公,那么确实可以了解低代码技术平台。流辰信息作为服务商,拥有较强的自主研发能力,根据市场的变化…...
26、类型别名
类型别名 顾名思义,其实就是类型类型起别名(新起一个名字) demo: type Name string; type NameConsole () > string; type NameUnite Name | NameConsole; function getName(n: NameUnite): Name {if( typeof n string)…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
