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

力扣146 - LRU缓存

视频讲解

哈希 + 双向链表

为什么要用双向链表?

快速删除节点(O(1))

如果是单链表的话,删除一个节点时,需要从头遍历,找到前驱节点,才能修改 prev->next,导致 O(n) 的时间复杂度

双向链表存储了两个指针,一个指针指向下一个节点,另一个指针指向上一个节点(前驱指针)。所以我们可以根据前驱指针快速找到上一个节点,然后移除掉当前节点。

demo:

class LRUCache {
public:struct Node{int key,val;Node *prev,*next;Node(int k,int v) : key(k) , val(v) , prev(nullptr) , next(nullptr){}};map<int,Node*>mp;Node *L,*R; //双哨兵int n; //LRU的总数//创建操作LRUCache(int capacity) {n = capacity;L = new Node(-1,-1);R = new Node(-1,-1);L->next = R;R->prev = L;}//获取值操作 (获得值的时候需要注意:如果有值存在哈希表中的话,那么就要将这个值放在最新的地方)//比如: L | 2 1 4 | R //我们查询1这个数,那么查完后需要变成: L | 2 4 1 | R int get(int key) {if(mp.count(key)){Node* node = mp[key];remove(node); //在链表中移除该节点 通过双向指针移除insert(node->key,node->val); // 在链表中插入该节点return node->val;}else{return -1;}}//插入操作void put(int key, int value) {if(mp.count(key)){Node* node = mp[key];remove(node);insert(key,value); //这里需要用给的key和value而不是node->key和node->val(因为可能插入的是新的值)}else{if(mp.size() == n){Node* node = L->next; //满了,需要移除的节点remove(node);insert(key,value);}else{insert(key,value);}}}//以下为自定义新增函数 remove是移除节点的函数 insert是插入节点的函数//同时在链表和哈希表中删除nodevoid remove(Node* node){Node* pre = node->prev;Node* nxt = node->next;pre->next = nxt;nxt->prev = pre;mp.erase(node->key);}//同样要同时操作链表和哈希表void insert(int key,int val){Node* node = new Node(key,val);Node* pre = R->prev;//这里是最后一个插入的数//向右pre->next = node;node->next = R;//向左node->prev = pre;R->prev = node;mp[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);*/

相关文章:

力扣146 - LRU缓存

视频讲解 哈希 双向链表 为什么要用双向链表&#xff1f; 快速删除节点&#xff08;O(1&#xff09;&#xff09; 如果是单链表的话&#xff0c;删除一个节点时&#xff0c;需要从头遍历&#xff0c;找到前驱节点&#xff0c;才能修改 prev->next&#xff0c;导致 O(n)…...

C++ 算法竞赛STL以及常见模板

目录 STL /*═══════════════ Vector ═══════════════*/ /*════════════════ Pair ════════════════*/ /*══════════════ String ════════════════*/ /*══════════…...

微信小程序将markdown内容转为pdf并下载

要在微信小程序中将Markdown内容转换为PDF并下载,您可以使用以下方法: 方法一:使用第三方API服务 选择第三方API服务: 可以选择像 Pandoc、Markdown-PDF 或 PDFShift 这样的服务,将Markdown转换为PDF。例如,PDFShift 提供了一个API接口,可以将Markdown内容转换为PDF格式…...

AI绘画软件Stable Diffusion详解教程(7):图生图基础篇(改变图像风格)

我们在使用AI魔盒不停的绘制一幅幅图像时&#xff0c;会有这样的疑问&#xff1a;为什么生成的图像随机性这么强&#xff1f;我们如何按照自己的构图创作作品&#xff1f;为什么提示词生成的图像细节不够&#xff1f;如何把手绘的风格转换成另一种风格&#xff0c;或者说把自己…...

ES映射知识

映射 映射类似于关系型数据库的Schema&#xff08;模式&#xff09;。 映射来定义字段列和存储的类型等基础信息。 {"mappings": {"properties": {"username": {"type": "keyword","ignore_above": 256 // 忽略…...

蓝桥杯嵌入式组第七届省赛题目解析+STM32G431RBT6实现源码

文章目录 1.题目解析1.1 分而治之&#xff0c;藕断丝连1.2 模块化思维导图1.3 模块解析1.3.1 KEY模块1.3.2 ADC模块1.3.3 IIC模块1.3.4 UART模块1.3.5 LCD模块1.3.6 LED模块1.3.7 TIM模块 2.源码3.第七届题目 前言&#xff1a;STM32G431RBT6实现嵌入式组第七届题目解析源码&…...

SpringBoot项目配置文件

SpringBoot项目提供了多种属性配置方式&#xff08;properties、yaml、yml&#xff09; yml配置文件 使用Apifox可以方便开发接口、前端测试等 工程搭建&#xff1a; 1.创建SpringBoot工程&#xff0c;并引入web开发起步依赖、mybatis、mysql驱动、lombok 2.创建数据库表&am…...

PythonWeb开发框架—Flask框架之flask-sqlalchemy、序列化和反序列化使用详解

1.安装依赖库 pip install flask-sqlalchemy pip install pymysql 2.连接数据库配置 from flask import Flask from flask_sqlalchemy import SQLAlchemyapp Flask(__name__) #创建 Flask 应用实例#配置数据库连接 app.config[SQLALCHEMY_DATABASE_URI]mysql://root:stud…...

如何监控 Pod 的 CPU/内存使用率,prometheus+grafana

一、监控 Pod 的 CPU/内存使用率的方法 1. 使用 kubectl top 命令&#xff08;临时检查&#xff09; # 查看所有 Pod 的资源使用率&#xff08;需安装 Metrics Server&#xff09; kubectl top pods --all-namespaces ​ # 查看指定命名空间的 Pod kubectl top pods -n <n…...

Spring Batch 概览

Spring Batch 是什么&#xff1f; Spring Batch 是 Spring 生态系统中的一个轻量级批处理框架&#xff0c;专门用于处理大规模数据任务。它特别适合企业级应用中需要批量处理数据的场景&#xff0c;比如数据迁移、报表生成、ETL&#xff08;Extract-Transform-Load&#xff09…...

用Deepseek写一个五子棋微信小程序

在当今快节奏的生活中&#xff0c;休闲小游戏成为了许多人放松心情的好选择。五子棋作为一款经典的策略游戏&#xff0c;不仅规则简单&#xff0c;还能锻炼思维。最近&#xff0c;我借助 DeepSeek 的帮助&#xff0c;开发了一款五子棋微信小程序。在这篇文章中&#xff0c;我将…...

AF3 squeeze_features函数解读

AlphaFold3 data_transforms 模块的 squeeze_features 函数的作用去除 蛋白质特征张量中不必要的单维度&#xff08;singleton dimensions&#xff09;和重复维度&#xff0c;以使其适配 AlphaFold3 预期的输入格式。 源代码&#xff1a; def squeeze_features(protein):&qu…...

Python 远程抓取服务器日志最后 1000行

哈喽&#xff0c;大家好&#xff0c;我是木头左&#xff01; 一、神奇的 Python 工具箱 1. SSH 连接的密钥——paramiko paramiko 库提供了丰富的方法来处理 SSH 连接的各种细节。从创建连接对象&#xff0c;到执行远程命令&#xff0c;再到获取命令输出&#xff0c;它都能有…...

vue3+screenfull实现部分页面全屏(遇到的问题会持续更新)

需求&#xff1a;除了左侧菜单&#xff0c;右侧主体部分全部全屏 首先下载screenfull全屏插件 npm install screenfull --save页面引入 import screenfull from screenfull;我这里是右上角全屏图标 <el-iconref"elIconRef"color"#ffffff"size"2…...

Ubuntu 下 nginx-1.24.0 源码分析 (1)

main 函数在 src\core\nginx.c int ngx_cdecl main(int argc, char *const *argv) {ngx_buf_t *b;ngx_log_t *log;ngx_uint_t i;ngx_cycle_t *cycle, init_cycle;ngx_conf_dump_t *cd;ngx_core_conf_t *ccf;ngx_debug_init(); 进入 main 函数 最…...

2025数据存储技术风向标:解析数据湖与数据仓库的实战效能差距

一、技术演进的十字路口 当前全球数据量正以每年65%的复合增长率激增&#xff0c;IDC预测到2027年企业将面临日均处理500TB数据的挑战。在这样的背景下&#xff0c;传统数据仓库与新兴数据湖的博弈进入白热化阶段。Gartner最新报告显示&#xff0c;采用混合架构的企业数据运营效…...

探索高性能AI识别和边缘计算 | NVIDIA Jetson Orin Nano 8GB 开发套件的全面测评

随着边缘计算和人工智能技术的迅速发展&#xff0c;性能强大的嵌入式AI开发板成为开发者和企业关注的焦点。NVIDIA近期推出的Jetson Orin Nano 8GB开发套件&#xff0c;凭借其40 TOPS算力、高效的Ampere架构GPU以及出色的边缘AI能力&#xff0c;引起了广泛关注。本文将从配置性…...

数据结构 常见的排序算法

&#x1f33b;个人主页&#xff1a;路飞雪吖~ &#x1f320;专栏&#xff1a;数据结构 目录 &#x1f33b;个人主页&#xff1a;路飞雪吖~ 一、插入排序 &#x1f31f;直接插入排序 &#x1f31f;希尔排序 二、选择排序 &#x1f31f;选择排序 &#x1f31f;堆排序…...

ES索引知识

索引是数据的载体&#xff0c;存储了文档和映射的信息 索引是具有相同结构的文档的合集体。 设置索引&#xff0c;不仅仅是设置索引名字&#xff0c;还有索引的一些配置&#xff0c;比如&#xff1a;分片和副本&#xff0c;刷新频率&#xff0c;搜索结果的最大参数&#xff0c…...

FreeRTOS第17篇:FreeRTOS链表实现细节05_MiniListItem_t:FreeRTOS内存优化

文/指尖动听知识库-星愿 文章为付费内容,商业行为,禁止私自转载及抄袭,违者必究!!! 文章专栏:深入FreeRTOS内核:从原理到实战的嵌入式开发指南 1 为什么需要迷你列表项? 在嵌入式系统中,内存资源极其宝贵。FreeRTOS为满足不同场景需求,设计了标准列表项(ListItem_…...

虚拟光驱软件Daemon Tools Lite

链接&#xff1a;https://pan.quark.cn/s/ebc5b998a07bDaemon Tools Lite 是一款免费、稳定、方便、优秀的虚拟光驱软件。安装后会自动在资源管理器生成一个和真实光驱一样的盘符&#xff0c;让您像访问真正光驱一样来访问虚拟光驱。Daemon Tools Lite 还可以模拟备份并且合并保…...

Leetcode 数据结构刷题 ->链表1

[27. 移除元素]移除等于所给值的元素&#xff0c;我们可以直接使用双指针&#xff0c;对着来的。关键就是把不等于x的值&#xff08;我改一下&#xff0c;没用val&#xff09;&#xff0c;放到后面去&#xff0c;这样前面就全部都是不等于x值&#xff0c;再计数即可。看代码就对…...

【独家首发】Python扩展安全成熟度模型(PESMM v1.2):覆盖编译期/加载期/运行期的9维评分体系,仅限前500名开发者免费获取评估工具包

第一章&#xff1a;Python扩展模块安全概述Python 扩展模块&#xff08;如 C/C 编写的 .so/.dll 文件或 Cython 生成的二进制模块&#xff09;在提升性能的同时&#xff0c;也引入了原生层特有的安全风险。与纯 Python 代码不同&#xff0c;扩展模块直接操作内存、调用系统 API…...

STM32串口环形队列IAP固件更新方案

基于STM32串口环形队列的IAP实现方案1. 项目概述1.1 系统架构本方案实现了一种基于STM32F103C8T6微控制器的串口IAP(In-Application Programming)系统&#xff0c;采用环形队列缓冲机制解决有限SRAM空间下的固件更新问题。系统将64KB Flash空间划分为四个功能区域&#xff1a;B…...

避免Java Stream重复消费:高效过滤Map的策略

本文旨在解决Java Stream在多过滤场景中常见的IllegalStatexception&#xff0c;即流被重复消耗的问题。我们将深入讨论Java Stream的单次使用特性&#xff0c;通过将外部过滤条件转换为集合&#xff0c;优化Map的过滤操作&#xff0c;提供高效、符合最佳实践的解决方案&#x…...

从Debezium到Flink RowData:手把手解析Flink CDC 2.3如何优雅处理MySQL的UPDATE事件

从Debezium到Flink RowData&#xff1a;深入解析Flink CDC 2.3处理MySQL UPDATE事件的机制 在实时数据处理的领域中&#xff0c;变更数据捕获(CDC)技术已经成为构建数据管道的核心组件。当MySQL数据库中的一条记录被更新时&#xff0c;如何准确捕获这一变更并将其高效地传递到下…...

手把手教你用STM32实现BLDC电机的SPWM控制(附代码调试心得)

STM32实战&#xff1a;无刷直流电机SPWM控制全解析与代码优化指南 从理论到实践&#xff1a;BLDC电机控制的核心逻辑 第一次接触无刷直流电机(BLDC)控制时&#xff0c;我被它优雅的工作原理所吸引——没有电刷的火花和磨损&#xff0c;却能实现高效的能量转换。在工业自动化、无…...

LeetDown完全指南:系统降级功能解决A6/A7设备用户的卡顿痛点

LeetDown完全指南&#xff1a;系统降级功能解决A6/A7设备用户的卡顿痛点 【免费下载链接】LeetDown a GUI macOS Downgrade Tool for A6 and A7 iDevices 项目地址: https://gitcode.com/gh_mirrors/le/LeetDown LeetDown是一款专为macOS设计的图形化降级工具&#xff0…...

开源工具赋能PS4玩家:GoldHEN Cheats Manager的全方位游戏体验优化方案

开源工具赋能PS4玩家&#xff1a;GoldHEN Cheats Manager的全方位游戏体验优化方案 【免费下载链接】GoldHEN_Cheat_Manager GoldHEN Cheats Manager 项目地址: https://gitcode.com/gh_mirrors/go/GoldHEN_Cheat_Manager GoldHEN Cheats Manager是一款专为PlayStation …...

C++vector,智能指针,拷贝构造函数

我将分别介绍 C 中的智能指针、std::vector 动态数组以及拷贝构造函数的概念、用法和适用场景。一、C 智能指针智能指针是用于自动化管理动态分配内存的模板类&#xff0c;位于 <memory> 头文件中。它们通过 RAII&#xff08;Resource Acquisition Is Initialization&…...