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

算法知识点————【LRU算法】

思想:淘汰最久没有使用的
应用场景:手机清后台的时候先清最久没有使用的应用
设计一种数据结构:接收一个 capacity 参数作为缓存的最大容量,然后实现两个 API,一个是 put(key, val) 方法存入键值对,另一个是 get(key) 方法获取 key 对应的 val,如果 key 不存在则返回 -1。要求:get 和 put 方法必须都是 O(1) 的时间复杂度。
在这里插入图片描述
在这里插入图片描述
哈希链表:哈希的查找配合双向链表的快速插入和删除
在这里插入图片描述

class Node{
public:int key,value;Node *prev,*next;Node(int k =0 ,int v =0 ) : key(k),value(v){}
};
class LRUCache{
private:int capacity;Node* dummy;//哨兵unordered_map<int,Node*> key_to_value;//删除节点void remove(Node * x){x->prev->next = x->next;x->next->prev = x->prev;}//添加节点 放到最上面void put_front(Node * x){x->prev = dummy;x->next = dummy->next;x->prev->next = x;x->next->prev = x;}  //获取节点 抽出放在最上面Node* get_node(int key){auto it = key_to_value.find(key);if(it == key_to_value.end()) return nullptr;//没找到auto node = it->second;//找到的话 map的node节点返回remove(node);put_front(node);return node;}
public:LRUCache(int capacity) : capacity(capacity),dummy(new Node()){dummy->prev  = dummy;dummy->next = dummy;}int get(int key){auto node = get_node(key);return node? node->value:-1;}void put(int key,int value){auto node = get_node(key);if(node){//有这本书node->value = value;return ;}key_to_value[key] = node = new Node(key,value);//没有这本书put_front(node);//添加if(key_to_value.size() > capacity){//添加得判断auto node_back = dummy->prev;key_to_value.erase(node_back->key);remove(node_back);delete node_back;}}};

相关文章:

算法知识点————【LRU算法】

思想&#xff1a;淘汰最久没有使用的 应用场景&#xff1a;手机清后台的时候先清最久没有使用的应用 设计一种数据结构&#xff1a;接收一个 capacity 参数作为缓存的最大容量&#xff0c;然后实现两个 API&#xff0c;一个是 put(key, val) 方法存入键值对&#xff0c;另一个是…...

记一次MySQL视图查询优化的经验

背景&#xff1a;库房系统项目迁移&#xff0c;两个版本的结构发生了很大变化&#xff0c;新版本的库存系统在开发阶段由于数据量小&#xff0c;根据看不出查询的性能问题&#xff0c;还沾沾自喜的想新版本多好。但是在做同步之后&#xff08;规则变更&#xff0c;需要插入很多…...

Cloudways搭建WordPress外贸独立站完整教程(1)

验证邮件发送完成后&#xff0c;就等待Cloudways的回复邮件&#xff0c;一般24小时之内就会收到激活的邮件。 Cloudways账号升级 激活成功后还需要账户升级&#xff0c;Cloudways提供了为期3天的免费试用体验。如果在试用期结束之前未绑定信用卡以升级账户&#xff0c;试用期…...

Delphi5数据控制组件——查询

文章目录 效果图参考查询Free方法Close方法总结通俗理解 完整代码 效果图 参考 本文是在上一篇的基础上&#xff0c;将查询页面重新写一次。 查询 {点击查询} procedure TForm2.Button1Click(Sender: TObject); vartj,tj1,tj2,tj3,tj4,tj5,tj6,tj7:string; begin//按照工号查…...

git pull之后发现项目错误,如何回到之前的版本方法

目录 首先我们打开小程序的cmd的黑窗口&#xff0c;git reflog查看之前的版本 之后再git reset --hard main{1} 我这个就已经返回了之前的6daaa2e的版本了 首先我们打开小程序的cmd的黑窗口&#xff0c;git reflog查看之前的版本 之后再git reset --hard main{1} 我这个就已…...

防跌倒识别摄像机

防跌倒识别摄像机 是一种结合了人工智能技术和监控摄像技术的先进设备&#xff0c;旨在通过实时监测和分析监控画面中的行为动作&#xff0c;及时发现并预防跌倒事件的发生。这种摄像机在医疗、养老院、家庭等场所有着广泛的应用前景。 防跌倒识别摄像机在医疗领域具有重要意义…...

MyQql性能诊断与实践

获取更多免费资料&#xff0c;见下图...

有序序列判断

描述 输入一个整数序列&#xff0c;判断是否是有序序列&#xff0c;有序&#xff0c;指序列中的整数从小到大排序或者从大到小排序(相同元素也视为有序)。 数据范围&#xff1a;3 < n< 50 序列中的值都满足 1< val < 100 输入描述&#xff1a; 第一行输入一个整数N…...

【Kubernetes知识点问答题】健康检查

目录 1. Kubernetes 对集群 Pod 和容器健康状态如何进行监控和检测的。 2. 解释 LivenessProbes 探针的作用及其适用场景。 3. 解释 ReadinessProbe 探针的作用及其适用场景。 4. 解释 StartupProbe 探针的作用及其适用场景。 5. 说明 K8s 中 Pod 级别的 Graceful Shutdown…...

【Prometheus】PromQL数据类型以及常用的计算函数用法详解

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

STM32高级定时器生成互补PWM的原理与代码实现

文章目录 前言一 CubeMx配置1.1 TIM1 Mode and Configuration1.2 Paramter Settings 二 程序代码三 仿真分析总结 前言 互补 PWM&#xff08;Complementary PWM&#xff09;是指一对逻辑状态互为反相的 PWM&#xff08;脉冲宽度调制&#xff09;信号。这种信号配置常见于电机控…...

双指针题总结

双指针题总结 hot100移动零盛水最多的容器三数之和接雨水最小覆盖子串 hot100 移动零 题目链接&#xff1a; 283.移动零 代码&#xff1a; class Solution {public void moveZeroes(int[] nums) {int slow 0;for (int fast 0; fast < nums.length; fast ){if (nums[fas…...

[数据集][目标检测]人脸口罩佩戴目标检测数据集VOC+YOLO格式8068张3类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;8068 标注数量(xml文件个数)&#xff1a;8068 标注数量(txt文件个数)&#xff1a;8068 标注…...

JVM3-双亲委派机制

目录 概述 作用 如何指定加载类的类加载器&#xff1f; 面试题 打破双亲委派机制 自定义类加载器 线程上下文类加载器 Osgi框架的类加载器 概述 由于Java虚拟机中有多个类加载器&#xff0c;双亲委派机制的核心是解决一个类到底由谁加载的问题 双亲委派机制&#xff…...

经典文献阅读之--DEviLOG(使用合成数据和真实世界数据的数据驱动占用网格映射基于Transformer的BEV方案量产方案)

0. 简介 在自动驾驶汽车&#xff08;AV&#xff09;的感知任务中&#xff0c;数据驱动的方法往往优于传统方法。这促使我们开发了一种基于数据的方法来从激光雷达测量中计算占用网格地图&#xff08;OGM&#xff09;。我们的方法扩展了之前的工作&#xff0c;使得估计的环境表…...

ssh之登录服务器后,自动进入目录(四十七)

简介&#xff1a; CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布&#xff1a;《Android系统多媒体进阶实战》&#x1f680; 优质专栏&#xff1a; Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a; 多媒体系统工程师系列【…...

如何看待IBM中国研发部裁员?

背景&#xff1a; 近日&#xff0c;IBM中国宣布撤出在华两大研发中心&#xff0c;引发了IT行业对于跨国公司在华研发战略的广泛讨论。这一决定不仅影响了众多IT从业者的职业发展&#xff0c;也让人思考全球化背景下中国IT产业的竞争力和未来发展方向。面对这一突如其来的变化&…...

计算机毕业设计选题推荐-土地承包管理系统-Java/Python项目实战(亮点:数据可视化分析、账号锁定、智能推荐)

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...

2024年高校辅导员考试题库及答案

一、判断题 121.高校学生身份权是基于高等教育的性质&#xff0c;学生应该获得的本体性权利。 答案&#xff1a;正确 122.学费占年生均教育培养成本的比例和标准由财政部制定。 答案&#xff1a;错误 123.享受国家专业奖学金的高校学生免缴学费。 答案&#xff1a;错误 124…...

使用python对股票市场进行数据挖掘的书籍资料有哪些

炒股自动化&#xff1a;申请官方API接口&#xff0c;散户也可以 python炒股自动化&#xff08;0&#xff09;&#xff0c;申请券商API接口 python炒股自动化&#xff08;1&#xff09;&#xff0c;量化交易接口区别 Python炒股自动化&#xff08;2&#xff09;&#xff1a;获取…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...