leetcode 面试150之 156.LUR 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中,则返回关键字的值,否则返回-1。void put(int key, int value)如果关键字key已经存在,则变更其数据值value;如果不存在,则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
题目重点:O(1)实现查找和删除
O(1)查找我们可以通过unordered_map底层哈希表来实现
这里我们如果缓存满了还得删除最久未使用关键字 ,所以我们得使用一个O(1)维护的“使用队列”,数组我们无法实现O(1)删除,而双向链表能实现O(1)删除,但是无法实现O(1)查询
所以我们这里用到了unordered_map<int,listnode*>映射为listnode*,通过map去实现O(1)查询
而listnode*双向链表实现O(1)插入和删除
起初我并未想到用双向链表而是用deque去维护“使用队列”,后者在维护队列无法做到O(1),包超时的
上代码:
class LRUCache {
public:struct listnode{int key;int val;listnode* pre;listnode* next;listnode(int k,int v):key(k),val(v),pre(nullptr),next(nullptr){}};int max_; //最大空间listnode* head; //头哨兵节点listnode* tail; //尾哨兵节点unordered_map<int,listnode*> dp; //精华//初始化 LRUCache(int capacity) {max_=capacity;head=new listnode(0,0);tail=new listnode(0,0);head->next=tail;tail->pre=head;}//双向链表头插法 将处理的node节点 使用优先级提高void addnode(listnode* node){node->next=head->next;head->next->pre=node;head->next=node;node->pre=head;}//断开node节点 并未delete void remove_node(listnode* node){node->pre->next=node->next;node->next->pre=node->pre;}//查询数据int get(int key) {if(dp.count(key)) //查询成功 提高该节点的“使用队列”优先级{remove_node(dp[key]);addnode(dp[key]);return dp[key]->val;}else return -1;}//插入数据void put(int key, int value) {if(dp.count(key)){dp[key]->val=value; //已经存在 更新val后,取走节点后插入头 提高优先级remove_node(dp[key]);addnode(dp[key]);}//key不存在else{if(max_==dp.size()) //空间已满 删除优先级低节点 也就是 tail->pre{listnode* temp=tail->pre;remove_node(temp);dp.erase(temp->key);delete temp; //释放内存}//无论空间是否够 都需要插入这个key节点listnode* node=new listnode(key,value); addnode(node);dp.insert({key,node});}}
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/
相关文章:
leetcode 面试150之 156.LUR 缓存
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -…...
启发式搜索算法复现
🏡作者主页:点击! 🤖编程探索专栏:点击! ⏰️创作时间:2024年11月21日19点05分 神秘男子影, 秘而不宣藏。 泣意深不见, 男子自持重, 子夜独自沉。 论文链接 点击开启你的论文编程之旅…...
【IDE】使用指南
定期更新实用技能,建议关注收藏点赞。 友情链接: 点击跳转常见代码编辑器的报错解决方案 目录 常用快捷键pycharm右下角边栏脚本头安装IDE的插件git配置TODO 代码编辑器里有许多小技巧,便于办公。本篇主要以pycharm,vscode等主流常用IDE为…...
设计编程网站集:简述可扩展性系统设计(笔记)
视频连接:简述可扩展性系统设计 三个关键原则 无状态 松散耦合 异步处理 扩展 负载均衡 缓存 分片...
「Mac玩转仓颉内测版25」基础篇5 - 布尔类型详解
本篇将介绍 Cangjie 中的布尔类型,包括布尔值的定义、运算操作符、逻辑运算、布尔类型的常见应用场景及其在条件判断中的应用,帮助开发者理解和使用布尔类型。 关键词 布尔类型定义布尔运算逻辑运算符条件判断常见应用场景 一、布尔类型概述 布尔类型&…...
Fashion-VDM:引领视频虚拟试穿技术的新篇章
引言 随着虚拟现实和增强现实技术的飞速发展,视频虚拟试穿(VVT)已成为时尚产业的一大创新领域。然而,现有的VVT方法在服装细节和时间一致性方面仍存在诸多不足。为了解决这些问题,Johanna Karras等人提出了Fashion-VDM,一种基于视频扩散模型(VDM)的新型视频虚拟试穿技…...
Scala中的集合复习(1)
Map、Set、Array、List 一、集合的三大类 1.序列Seq表示有先后顺序的集合。(Array、List) 2.集Set:表示无序且不重复的集合。 3.映射Map:表示键值对。 Stack:栈,特点是:后进先出。 packag…...
Java依赖包漏洞检测命令
1、漏洞扫描工具 maven插件方式:Dependency-Check 2、命令 检查单个 Maven 工程的安全漏洞 mvn dependency-check:check 这个命令会在 target 目录下生成一个 dependency-check-report.html 文件,其中包含了依赖项的安全漏洞分析报告。 检查多个 M…...
【Java】强制类型转换
int a23; short b(short) a; 小的接受大的接受不了,强制类型转换. 带有Buffer的,带有流的,都是数组。 网络流,文件流都是数组. 这种就是流。 操作系统底层就是C. 没有直系关系的,不让转换 语法不报错,运行…...
RabbitMQ消息可靠性保证机制4--消费端限流
7.7 消费端限流 在类似如秒杀活动中,一开始会有大量并发写请求到达服务端,城机对消息进行削峰处理,如何做? 当消息投递的速度远快于消费的速度时,随着时间积累就会出现“消息积压”。消息中间件本身是具备一定的缓冲…...
查找萤石云IOS Sdk中的编解码接口
2021/1/20 以前的时候,碰到的问题,想把萤石云视频介入到TRTC,但是... 萤石云的IOS接口中没有相应的解码播放库,也就是找不到PlayerSDK对应部分,怎么做呢? 一个是坐等萤石云开放这部分接口,可能…...
erchas
#include <iostream> #include <vector> https://gitee.com/tongchaowei/front-native-page-template/tree/main/image-display/template-01 using namespace std; class BinaryTree { private: vector<char> tree; // 存储二叉树的数组 int size;…...
【网络安全】SSL(一):为什么需要 Keyless SSL?
未经许可,不得转载。 文章目录 背景正文背景 随着网站和应用程序向云端迁移,使用 HTTPS(SSL/TLS)加密流量已成为行业标准。然而,传统的 HTTPS 配置要求服务器持有网站的私钥,这在云计算环境中引发了一系列安全性和合规性问题。一旦云服务器遭到攻击,私钥泄露可能带来不…...
ggplot2 分面图等添加注释文字,相加哪里加哪里: 自定义函数 AddText()
如果分面图上还想再添加文字,只能使用底层的grid包了。 函数定义 # Add text to ggplot2 figures # # param label text you want to put on figure # param x position x, left is 0, right 1 # param y position y, bottom is 0, up 1 # param color text color…...
解读缓存问题的技术旅程
目录 前言1. 问题的突发与初步猜测2. 缓存的“隐身术”3. 缓存策略的深层优化4. 反思与感悟结语 前言 那是一个普通的工作日,团队例行的早会刚刚结束,我正准备继续优化手头的模块时,突然收到了用户反馈。反馈的内容是部分数据显示异常&#…...
洛谷P1597
语句解析 - 洛谷 语句解析 题目背景 木有背景…… 题目描述 一串长度不超过255的 PASCAL 语言代码,只有 a,b,c 三个变量,而且只有赋值语句,赋值只能是一个一位的数字或一个变量,每条赋值语句的格式是 [变量]:[变量或一位整数…...
2411rust,76~79
1.76.0稳定版 此版本较小 ABI兼容更新 函数指针文档中新增的ABI兼容部分介绍了函数签名与ABI兼容的意义.大部分是参数类型和返回类型的兼容,及在当前Rust中兼容的列表.文档仅描述现有兼容的状态. 一个新增功能是,现在保证符和u32是ABI兼容的.它们一直有相同大小和对齐方式,…...
vue2.0前端管理系统界面布局设置
前言 后台管理系统的核心就是用户管理、角色管理(含权限分配)、菜单管理,以及一些业务管理。业务管理通常以及根据不同的角色进行了权限分配。本次任务完成用户管理页面。 一 界面设计 1.引用Element 的Container 布局容器。 以上次博客中…...
4. SQL视图
MySQL中的视图(View)是一种虚拟表,本质是存储了一条SELECT语句。视图并不直接存储数据,而是动态生成结果集,帮助开发者简化查询逻辑和增强数据安全性。本文将从视图的基础概念到实际应用,逐步深入地探讨如何…...
Simulink学习笔记【PID UG联动仿真】
Simulink进行PID控制及调参: 建立系统动力学框图(把状态方程翻译出来),设置成subsystem建立PID反馈回路。示波器叫scope,多变量输出用demux和mux。可以用自动调参Tune模块,调整响应速度和稳定性࿰…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
