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

*算法中的数据结构(3)

持续更新···

1.单调栈

它依旧是⼀个栈结构,只不过⾥⾯存储的数据是递增或者递减的。
2. 单调栈解决的问题
*寻找当前元素左侧,离它最近,并且⽐它⼤的元素在哪;
• 寻找当前元素左侧,离它最近,并且⽐它⼩的元素在哪;
• 寻找当前元素右侧,离它最近,并且⽐它⼤的元素在哪;
• 寻找当前元素右侧,离它最近,并且⽐它⼩的元素在哪。
寻找当前元素左侧,离它最近,并且比它大的元素在哪
从左往右遍历元素,构造⼀个单调递减的栈。插⼊当前位置的元素的时:
如果栈为空,则左侧不存在⽐当前元素⼤的元素;
如果栈⾮空,插⼊当前位置元素时的栈顶元素就是所找的元素。
注意,因为我们要找的是最终结果的位置。因此,栈⾥⾯存的是每个元素的下标。

2.单调队列

这⾥的队列和普通的队列不⼀样,是⼀个双端队列
2. 单调队列解决的问题
⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题,以及优化动态规划。
【题⽬描述】
有⼀个⻓为n 的序列a ,以及⼀个⼤⼩为k 的窗⼝。现在这个从左边开始向右滑动,每次滑动⼀
个单位,求出每次滑动后窗⼝中的最⼤值和最⼩值。
【输⼊描述】
输⼊⼀共有两⾏,第⼀⾏有两个正整数 n , k 。 第⼆⾏ n 个整数,表⽰序列 a
【输出描述】
输出共两⾏,第⼀⾏为每次窗⼝滑动的最⼩值
第⼆⾏为每次窗⼝滑动的最⼤值
窗⼝内最⼤值:
从左往右遍历元素,维护⼀个单调递减的队列:
当前元素进队之后,注意维护队列内的元素在⼤⼩为 k 的窗⼝内;
此时队头元素就是最⼤值。

3.并查集

在实现并查集的时,我们⼀般让根节点⾃⼰指向⾃⼰
在有些问题中,我们需要维护若⼲个集合,并且基于这些集合要频繁执⾏下⾯的操作:
查询操作:查找元素x 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表,查询的是
这个集合中的代表元素;
合并操作:将元素 x所在的集合与元素 y所在的集合合并成⼀个集合;(注意,合并的是元素所
在的集合,不是这两个元素!)
判断操作:判断元素 x y 是否在同⼀个集合。
并查集(Union Find):是⼀种⽤于维护元素所属集合 的数据结构,实现为⼀个森林,其中每棵树表 ⽰⼀个集合,树中的节点表⽰对应集合中的元素,根节点来代表整个集合。

4.扩展域并查集

将每个元素拆分成多个域,每个域代表⼀种状态或者关系。
通过维护这些域之间的关系,来处理复杂的约束条件。
敌⼈朋友问题中,我们会将 x 分成两个域,朋友域 x 以及敌⼈域 y
x y 是朋友,正常处理,把 x y 合并成⼀个集合;
• x 和y 是敌⼈:那么 x和y 的敌⼈y+n 就是朋友,合并 x与y+n ;y 和x 的敌⼈x+n
就是朋友,合并 y与x+n 。
这样就可以利⽤两个域,将所有的关系维护起来。
【问题:食物链】
针对 x ,扩展三个域:同类域 x,捕⻝域 x + n,被捕⻝域 x + n + n。
如果 x 和 y 是同类:
x 和 y 是同类
x + n 与 y + n 是同类
x + n + n 与 y + n + n 是同类
如果 x 捕⻝ y:
x + n 与 y 同类
x 与 y + n + n 同类
x + n + n 与 y + n 同类

5.带权并查集

带权并查集在普通并查集的基础上,为每个结点增加了⼀个权值。这个权值可以表⽰当前结点与⽗结点之间的关系、距离或其他信息(注意,由于我们有路径压缩操作,所以最终这个权值表⽰的是当前结点相对于根结点的信息)。有了这样⼀个权值,就可以推断出集合中各个元素之间的相互关系。

 【问题:食物链】

把真话⾥⾯的相互关系,⽤"带权并查集"维护起来,权值表⽰当前节点相对于根节点的距离。那么对于集合中的任意两点 x y
如果 ( d [ y ] − d [ x ]) % 3 == 0 ,表⽰两者是同类关系;
如果 ( d [ y ] − d [ x ]) % 3 == 1 ,表⽰两者是捕⻝关系;
如果 ( d [ y ] − d [ x ]) % 3 == 2 ,表⽰两者是天敌关系。
find 操作:
更新 d 数组:按照最基础的距离更新的⽅式, d[x] = d[x] + d[fa[x]]
union 操作:
如果 x y 是同类,那么边权就是 0
如果 x y ,那么边权就是 1

6.字符串哈希

定义⼀个把字符串映射到整数的函数 ,这就是字符串哈希。就是将⼀个字符串⽤⼀个整数表示。
单次计算⼀个字符串的哈希值复杂度是O ( N ) 。如果需要多次询问⼀个字符串的⼦串的哈希值,每次重新计算效率⾮常低下。
⼀般利⽤前缀和思想先预处理字符串中每个前缀的哈希值,这样的话每次就能快速求出⼦串的哈希
了。

7.tree树

Trie 树⼜叫字典树或前缀树,是⼀种能够快速插⼊和查询字符串的数据结构。它利⽤字符串的公共前缀,将字符串组织成⼀棵树形结构,从⽽⼤⼤提⾼了存储以及查找效率。
字典树作用:
• 查询某个单词是否出现过,并且出现⼏次;
• 查询有多少个单词是以某个字符串为前缀;
• 查询所有以某个前缀开头的单词;(这个作⽤可以⽤到输⼊法中,输⼊拼⾳的时候,可以提⽰可能
的单词)

相关文章:

*算法中的数据结构(3)

持续更新 1.单调栈 它依旧是⼀个栈结构,只不过⾥⾯存储的数据是递增或者递减的。 2. 单调栈解决的问题 *寻找当前元素左侧,离它最近,并且⽐它⼤的元素在哪; • 寻找当前元素左侧,离它最近,并且⽐它⼩的元素…...

【大模型系列篇】国产开源大模型DeepSeek-V3技术报告解析

DeepSeek-V3技术报告 目录 DeepSeek-V3技术报告 1. 摘要 2. 引言 3. DeepSeek V3 架构 3.1 基础架构 3.1.1. 多头潜在注意力 3.1.2. DeepSeekMoE和无辅助损失的负载均衡 3.2 多令牌预测 4. 基础设施 4.1 计算集群 4.2 训练框架 4.2.1. DualPipe算法与计算通信协同优…...

MyBatisPlus搭建教程

简介 搭建MyBatisPlus2.x 构建项目 配置Maven 引入依赖 springboot <dependency><groupId>mysql</groupId><artifactId>mysql-connector-java</artifactId></dependency><dependency><groupId>com.alibaba</groupId>&l…...

【商城实战(2)】商城架构设计:从底层逻辑到技术实现

【商城实战】专栏重磅来袭&#xff01;这是一份专为开发者与电商从业者打造的超详细指南。从项目基础搭建&#xff0c;运用 uniapp、Element Plus、SpringBoot 搭建商城框架&#xff0c;到用户、商品、订单等核心模块开发&#xff0c;再到性能优化、安全加固、多端适配&#xf…...

数据序列化协议 Protobuf 3 介绍(Go 语言)

Protobuf 3 入门 1. 什么是序列化&#xff1f; 1.1 概念 序列化&#xff08;Serialization 或 Marshalling&#xff09; 是指将数据结构或对象的状态转换成可存储或传输的格式。反向操作称为反序列化&#xff08;Deserialization 或 Unmarshalling&#xff09;&#xff0c;它…...

从芯片到光网络:解密平面光波导技术(PLC)核心优势

关键词&#xff1a;PLC、OFDR、光链路检测 平面光波导技术&#xff08;Planar Lightwave Circuit, PLC&#xff09;是一种基于平面波导结构的光学器件制造技术。它通过在平面基底上制作光波导&#xff0c;实现光信号的传输、分路、耦合、调制等功能。PLC技术的核心在于利用光波…...

5分钟快速搭建一个 SpringBoot3 + MyBatis-Plus 工程项目

环境 idea 2023.3.5 jdk 17 mysql 8 创建SpringBoot工程 创建SpringBoot工程&#xff0c;这里有两种方式可选&#xff0c;一种是使用idea提供的Spring Initializr自动创建&#xff0c;一种是通过Maven Archetype手动创建 自动创建SpringBoot工程 使用Spring Initializr创建…...

如何判断https使用了哪个版本的TLS?

互联网各领域资料分享专区(不定期更新): Sheet 正文 一、使用浏览器开发者工具(适合普通用户) 1. Google Chrome 打开目标网站(如 https://example.com)。点击地址栏左侧的 锁形图标。选择 「连接是安全的」 → 「证书信息」。在证书详情中,查看 「技术详细信息」 或 「…...

如何在 NocoBase 中实现 CRM 的线索转化

1. 引言 本教程将一步一步地引导您如何在 NocoBase 中实现 CRM 的商机转化&#xff08;Opportunity Conversion&#xff09;功能。我们将介绍如何创建所需的 collections&#xff08;数据表&#xff09;、配置数据管理页面、设计转化流程以及设置关联管理&#xff0c;从而帮助…...

StarRocks-fe工程在Cursor中不能识别为Java项目

SR简介 StarRocks 是一款高性能分析型数据库&#xff0c;支持实时、多维度、高并发的数据分析。本指南旨在解决在使用 VSCode 或 Cursor 开发 StarRocks 后端项目时遇到的模块识别问题。 问题描述 使用 Cursor 或 VSCode 打开 StarRocks 的后端工程 fe 时&#xff0c;spark-…...

影刀RPA开发拓展--SQL常用语句全攻略

前言 SQL&#xff08;结构化查询语言&#xff09;是数据库管理和操作的核心工具&#xff0c;无论是初学者还是经验丰富的数据库管理员&#xff0c;掌握常用的 SQL 语句对于高效管理和查询数据都至关重要。本文将系统性地介绍最常用的 SQL 语句&#xff0c;并为每个语句提供详细…...

05类加载机制篇(D6_方法调用和方法执行)

目录 一、字节码指令集 二、基本数据类型 1. 加载和存储指令 2. const系列 3. push系列 4. ldc系列 5. load系列 load系列A load系列B 6. store系列 store系列A store系列B 7. pop系列 8. 栈顶元素数学操作及移位操作系列 9. 运算指令 10. 类型转换指令 11. 宽…...

视音频数据处理入门:颜色空间(二)---ffmpeg

目录 概述 流程 相关流程 初始化方法 初始化代码 转换方法 转换代码 释放方法 整体代码介绍 代码路径 概述 本篇简单说一下基于FFmpeg的libswscale的颜色空间转换&#xff1b;Libswscale里面实现了各种图像像素格式的转换&#xff0c;例如&#xff1a;YUV与RGB之间的…...

从零开始:H20服务器上DeepSeek R1 671B大模型部署与压力测试全攻略

前言 最近&#xff0c;我有幸在工作中接触到了DeepSeek R1 671B模型&#xff0c;这是目前中文开源领域参数量最大的高质量模型之一。DeepSeek团队在2024年推出的这款模型&#xff0c;以其惊人的6710亿参数量和出色的推理性能&#xff0c;引起了业界广泛关注。 作为一名AI基础…...

【FAQ】HarmonyOS SDK 闭源开放能力 —Map Kit(5)

1.问题描述&#xff1a; 提供两套标准方案&#xff0c;可根据体验需求选择&#xff1a; 1.地图Picker(地点详情) 用户体验&#xff1a;①展示地图 ②标记地点 ③用户选择已安装地图应用 接入文档&#xff1a;https://developer.huawei.com/consumer/cn/doc/harmonyos-guide…...

Leetcode 3469. Find Minimum Cost to Remove Array Elements

Leetcode 3469. Find Minimum Cost to Remove Array Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3469. Find Minimum Cost to Remove Array Elements 1. 解题思路 这一题我没啥特别好的思路&#xff0c;就只能动态规划了&#xff0c;倒是也能过&#xff0c;不过总…...

Excel的行高、列宽单位不统一?还是LaTeX靠谱

想要生成田字格、米字格、带拼音标准&#xff0c;方便小学生书法和练字。Word&#xff0c;Excel之类所见即所得是最容易相当的方式。但它们处理带田字格之类背景时&#xff0c;如果没有专用模板、奇奇怪怪的插件&#xff0c;使用起来会碰到各种问题。比如&#xff0c;Word里面用…...

(新版本onenet)stm32+esp8266/01s mqtt连接onenet上报温湿度和远程控制(含小程序)

物联网实践教程&#xff1a;微信小程序结合OneNET平台MQTT实现STM32单片机远程智能控制 远程上报和接收数据——汇总 前言 之前在学校获得了一个新玩意&#xff1a;ESP-01sWIFI模块&#xff0c;去搜了一下这个小东西很有玩点&#xff0c;远程控制LED啥的&#xff0c;然后我就想…...

告别GitHub连不上!一分钟快速访问方案

一、当GitHub抽风时&#xff0c;你是否也这样崩溃过&#xff1f; &#x1f621; npm install卡在node-sass半小时不动&#x1f62d; git clone到90%突然fatal: early EOF&#x1f92c; 改了半天hosts文件&#xff0c;第二天又失效了... 根本原因&#xff1a;传统代理需要复杂…...

迷你世界脚本对象库接口:ObjectLib

对象库接口&#xff1a;ObjectLib 迷你世界 更新时间: 2023-04-26 20:21:09 具体函数名及描述如下: 序号 函数名 函数描述 1 getAreaData(...) 获取区域数据 2 getPositionData(...) 获取位置数据 3 getLivingData(...) 获取生物数据 4 getItemDat…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

从0开始学习R语言--Day17--Cox回归

Cox回归 在用医疗数据作分析时&#xff0c;最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据&#xff0c;往往会有很多的协变量&#xff0c;即使我们通过计算来减少指标对结果的影响&#xff0c;我们的数据中依然会有很多的协变量&#xff0c;且…...

(12)-Fiddler抓包-Fiddler设置IOS手机抓包

1.简介 Fiddler不但能截获各种浏览器发出的 HTTP 请求&#xff0c;也可以截获各种智能手机发出的HTTP/ HTTPS 请求。 Fiddler 能捕获Android 和 Windows Phone 等设备发出的 HTTP/HTTPS 请求。同理也可以截获iOS设备发出的请求&#xff0c;比如 iPhone、iPad 和 MacBook 等苹…...

【字节拥抱开源】字节团队开源视频模型 ContentV: 有限算力下的视频生成模型高效训练

本项目提出了ContentV框架&#xff0c;通过三项关键创新高效加速基于DiT的视频生成模型训练&#xff1a; 极简架构设计&#xff0c;最大化复用预训练图像生成模型进行视频合成系统化的多阶段训练策略&#xff0c;利用流匹配技术提升效率经济高效的人类反馈强化学习框架&#x…...