力扣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缓存
视频讲解 哈希 双向链表 为什么要用双向链表? 快速删除节点(O(1)) 如果是单链表的话,删除一个节点时,需要从头遍历,找到前驱节点,才能修改 prev->next,导致 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魔盒不停的绘制一幅幅图像时,会有这样的疑问:为什么生成的图像随机性这么强?我们如何按照自己的构图创作作品?为什么提示词生成的图像细节不够?如何把手绘的风格转换成另一种风格,或者说把自己…...
ES映射知识
映射 映射类似于关系型数据库的Schema(模式)。 映射来定义字段列和存储的类型等基础信息。 {"mappings": {"properties": {"username": {"type": "keyword","ignore_above": 256 // 忽略…...
蓝桥杯嵌入式组第七届省赛题目解析+STM32G431RBT6实现源码
文章目录 1.题目解析1.1 分而治之,藕断丝连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.第七届题目 前言:STM32G431RBT6实现嵌入式组第七届题目解析源码&…...
SpringBoot项目配置文件
SpringBoot项目提供了多种属性配置方式(properties、yaml、yml) yml配置文件 使用Apifox可以方便开发接口、前端测试等 工程搭建: 1.创建SpringBoot工程,并引入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 命令(临时检查) # 查看所有 Pod 的资源使用率(需安装 Metrics Server) kubectl top pods --all-namespaces # 查看指定命名空间的 Pod kubectl top pods -n <n…...
Spring Batch 概览
Spring Batch 是什么? Spring Batch 是 Spring 生态系统中的一个轻量级批处理框架,专门用于处理大规模数据任务。它特别适合企业级应用中需要批量处理数据的场景,比如数据迁移、报表生成、ETL(Extract-Transform-Load)…...
用Deepseek写一个五子棋微信小程序
在当今快节奏的生活中,休闲小游戏成为了许多人放松心情的好选择。五子棋作为一款经典的策略游戏,不仅规则简单,还能锻炼思维。最近,我借助 DeepSeek 的帮助,开发了一款五子棋微信小程序。在这篇文章中,我将…...
AF3 squeeze_features函数解读
AlphaFold3 data_transforms 模块的 squeeze_features 函数的作用去除 蛋白质特征张量中不必要的单维度(singleton dimensions)和重复维度,以使其适配 AlphaFold3 预期的输入格式。 源代码: def squeeze_features(protein):&qu…...
Python 远程抓取服务器日志最后 1000行
哈喽,大家好,我是木头左! 一、神奇的 Python 工具箱 1. SSH 连接的密钥——paramiko paramiko 库提供了丰富的方法来处理 SSH 连接的各种细节。从创建连接对象,到执行远程命令,再到获取命令输出,它都能有…...
vue3+screenfull实现部分页面全屏(遇到的问题会持续更新)
需求:除了左侧菜单,右侧主体部分全部全屏 首先下载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%的复合增长率激增,IDC预测到2027年企业将面临日均处理500TB数据的挑战。在这样的背景下,传统数据仓库与新兴数据湖的博弈进入白热化阶段。Gartner最新报告显示,采用混合架构的企业数据运营效…...
探索高性能AI识别和边缘计算 | NVIDIA Jetson Orin Nano 8GB 开发套件的全面测评
随着边缘计算和人工智能技术的迅速发展,性能强大的嵌入式AI开发板成为开发者和企业关注的焦点。NVIDIA近期推出的Jetson Orin Nano 8GB开发套件,凭借其40 TOPS算力、高效的Ampere架构GPU以及出色的边缘AI能力,引起了广泛关注。本文将从配置性…...
数据结构 常见的排序算法
🌻个人主页:路飞雪吖~ 🌠专栏:数据结构 目录 🌻个人主页:路飞雪吖~ 一、插入排序 🌟直接插入排序 🌟希尔排序 二、选择排序 🌟选择排序 🌟堆排序…...
ES索引知识
索引是数据的载体,存储了文档和映射的信息 索引是具有相同结构的文档的合集体。 设置索引,不仅仅是设置索引名字,还有索引的一些配置,比如:分片和副本,刷新频率,搜索结果的最大参数,…...
FreeRTOS第17篇:FreeRTOS链表实现细节05_MiniListItem_t:FreeRTOS内存优化
文/指尖动听知识库-星愿 文章为付费内容,商业行为,禁止私自转载及抄袭,违者必究!!! 文章专栏:深入FreeRTOS内核:从原理到实战的嵌入式开发指南 1 为什么需要迷你列表项? 在嵌入式系统中,内存资源极其宝贵。FreeRTOS为满足不同场景需求,设计了标准列表项(ListItem_…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
