BFS算法篇——打开智慧之门,BFS算法在拓扑排序中的诗意探索(下)
文章目录
- 引言
- 一、课程表
- 1.1 题目链接:https://leetcode.cn/problems/course-schedule/description/
- 1.2 题目分析:
- 1.3 思路讲解:
- 1.4 代码实现:
- 二、课程表||
- 2.1 题目链接:https://leetcode.cn/problems/course-schedule-ii/description/
- 2.2 题目分析:
- 2.3 思路讲解:
- 2.4 代码实现:
- 三、火星词典
- 3.1 题目链接:https://leetcode.cn/problems/Jf1JuT/description/
- 3.2 题目分析:
- 3.3 思路讲解:
- 3.4 代码实现:
- 小结

引言
上篇我们介绍了BFS解决拓扑排序的背景知识,本篇我们将结合具体题目分析,进一步深化对于该算法的理解运用。
一、课程表
1.1 题目链接:https://leetcode.cn/problems/course-schedule/description/
1.2 题目分析:
- numCourses 表示要学的课程的数量
- prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 如果存在能按照顺序学完的可能,返回true,否则返回false
1.3 思路讲解:
该题为一个明显的拓扑排序问题,根据上篇讲解,我们可以这样子处理
- 首先构建邻接表,先决条件pre表示的顺序即为b->a,作为边加入其中
- 同时,由于学习a之前必须要学习b,因此a的入度加1
- 之后将入度为0的节点入队列,层序遍历即可
1.4 代码实现:
class Solution {
public:bool canFinish(int n, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> edges;//邻接表vector<int> in(n);//入度//建图for(auto e: prerequisites){int a=e[0],b=e[1];edges[b].push_back(a);in[a]++;}queue<int> q;//将入度为0的节点入队列for(int i=0;i<n;i++){if(in[i]==0){q.push(i);}}//层序遍历while(q.size()){int t=q.front();q.pop();for(int e : edges[t]){in[e]--;if(in[e]==0){q.push(e);}}}for(int i=0;i<n;i++){if(in[i]){return false;}//说明无法学完所有课程}return true;}
};
二、课程表||
2.1 题目链接:https://leetcode.cn/problems/course-schedule-ii/description/
2.2 题目分析:
该题与上题要求基本相同,只是返回值要求返回可能的一种学习顺序,如果不存在,则返回空数组
2.3 思路讲解:
判断是否可以学习的思路与上题相同,我们只需要在层序遍历时,用一个数组记录当前学习顺序即可。
2.4 代码实现:
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> edges;//邻接表vector<int> in(numCourses);//入度vector<int> ret;//返回值vector<int> temp;//空数组queue<int> q;//建图for(auto e:prerequisites){int a=e[0],b=e[1];edges[b].push_back(a);in[a]++;}//入度为0的节点入队列for(int i=0;i<numCourses;i++){if(in[i]==0){q.push(i);}}while(q.size()){int t=q.front();q.pop();ret.push_back(t);//更新结果for(int e:edges[t]){in[e]--;if(in[e]==0){q.push(e);}}}for(int i=0;i<numCourses;i++){if(in[i]){return temp;}}//存在未完成情况,返回空数组return ret;}
};
三、火星词典
3.1 题目链接:https://leetcode.cn/problems/Jf1JuT/description/
3.2 题目分析:
题目要求一时间难以读懂,我们来简单翻译一下:
- 给定的word里面已经按一种新的字母顺序排列好
假设 words = [“wrt”,“wrf”,“er”,“ett”,“rftt”],我们可以得到字母之间的一些依赖关系:
-
比如从 “wrt” 和 “wrf” 可以得出 t 在 f 之前(因为 “t” 是两个单词中的不同字母,且在相同位置上不同)。
-
从 “er” 和 “ett” 中可以得出 r 在 e 之前。
最终需要返回题目中外星词典的递增顺序,若不存在合法的顺序,则返回空
3.3 思路讲解:
我们通过比较相邻的单词,找出它们的第一个不同字母。这些字母的顺序关系就可以帮助我们构建字母的顺序图。
图的构建:
- 我们可以通过图来表示字母之间的顺序关系。每个字母是图中的一个节点,而字母之间的顺序关系是边。
拓扑排序:
- 通过拓扑排序的方法,我们可以得到字母的正确排序。如果有环,则说明字母顺序无法确定,返回空字符串。
3.4 代码实现:
class Solution {
public:unordered_map<char,unordered_set<char>> edges;//边unordered_map<char,int> in;//入度bool check;//处理特殊情况void add(string& s1,string& s2){int n=min(s1.size(),s2.size());int i;for( i=0;i<n;i++){if(s1[i]!=s2[i]){char a=s1[i],b=s2[i];if(!edges.count(a) || !edges[a].count(b))//如果之前为记录过,则记录这条边a->b{edges[a].insert(b);in[b]++;//更新边和入度节点}break;//注意跳出循环}}if(i==s2.size()&&i<s1.size())//处理abc ab这种特殊情况{check=true;}}string alienOrder(vector<string>& words) {//建图和初始化for(auto e: words){for(auto ch:e){in[ch]=0;}//将所有字符的入度都初始化为0}int n=words.size();for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){add(words[i],words[j]);if(check){return "";//存在非法情况}}}//拓扑排序queue<char> q;string ret;//将所有入度为0的节点for(auto [a,b] :in){if(b==0){q.push(a);}}while(q.size()){char t=q.front();q.pop();ret+=t;for(auto e:edges[t]){if(--in[e]==0) q.push(e);}}for(auto [a,b] :in){if(b!=0){return "";}}//判断是否存在不合法顺序return ret;}
};
小结
本篇关于BFS解决拓扑排序的讲解就暂告段落啦,希望能对大家的学习产生帮助,欢迎各位佬前来支持斧正!!!
相关文章:
BFS算法篇——打开智慧之门,BFS算法在拓扑排序中的诗意探索(下)
文章目录 引言一、课程表1.1 题目链接:https://leetcode.cn/problems/course-schedule/description/1.2 题目分析:1.3 思路讲解:1.4 代码实现: 二、课程表||2.1 题目链接:https://leetcode.cn/problems/course-schedul…...
While语句数数字
import java.util.Scanner;public class Hello {public static void main(String[] args) {Scanner in new Scanner(System.in);int number in.nextInt();int count 0;while( number > 0 ){number number / 10;count count 1;}System.out.println(count);} }...
G1JVM内存分配机制详解
为什么堆内存不是预期的3G? 当您设置-XX:MaxRAMPercentage75时,JVM并不会简单地将容器内存(4G)的75%全部分配给堆,原因如下: 计算基准差异: 百分比是应用于"可用物理内存"而非"容器总内存" &q…...
“端 - 边 - 云”三级智能协同平台的理论建构与技术实现
摘要 随着低空经济与智能制造的深度融合,传统集中式云计算架构在实时性、隐私保护和资源效率上的瓶颈日益凸显。本文提出“端 - 边 - 云”三级智能协同平台架构,以“时空 - 资源 - 服务”三维协同理论为核心,构建覆盖终端感知、边缘计算、云端…...
【UAP】《Empirical Upper Bound in Object Detection and More》
Borji A, Iranmanesh S M. Empirical upper bound in object detection and more[J]. arXiv preprint arXiv:1911.12451, 2019. arXiv-2019 文章目录 1、Background and Motivation2、Related Work3、Advantages / Contributions4、Experimental Setup4.1、Benchmarks Dataset…...
Web Service及其实现技术(SOAP、REST、XML-RPC)介绍
一.概述 1.Web Service(Web 服务) Web Service 由万维网联盟 (W3C) 定义为一种软件系统,旨在支持通过网络进行可互操作的计算机间交互。 广义概念:基于 Web 技术(如 HTTP 协议)的跨平台、跨语言通信机制…...
基于Spring Boot+Layui构建企业级电子招投标系统实战指南
一、引言:重塑招投标管理新范式 在数字经济浪潮下,传统招投标模式面临效率低、透明度不足、流程冗长等痛点。本文将以Spring Boot技术生态为核心,融合Mybatis持久层框架、Redis高性能缓存及Layui前端解决方案,构建一个覆盖招标代理…...
【嵌入式】记一次解决VScode+PlatformIO安装卡死的经历
PlatformIO 是开源的物联网开发生态系统。提供跨平台的代码构建器、集成开发环境(IDE),兼容 Arduino,ESP8266和mbed等。 开源库地址:https://github.com/platformio 在 VScode 中配置 PlatformIO 插件,记录…...
抗量子计算攻击的数据安全体系构建:从理论突破到工程实践
在“端 - 边 - 云”三级智能协同理论中,端 - 边、边 - 云之间要进行数据传输,网络的安全尤为重要,为了实现系统总体的安全可控,将构建安全网络。 可先了解我的前文:“端 - 边 - 云”三级智能协同平台的理论建构与技术实…...
【FMMT】基于模糊多模态变压器模型的个性化情感分析
遇到很难的文献看不懂,不应该感到气馁,应该激动,因为外审估计也看不太懂,那么学明白了可以吓唬他 缺陷一:输入依赖性与上下文建模不足 缺陷描述: 传统自注意力机制缺乏因果关系,难以捕捉序列历史背景多模态数据间的复杂依赖关系未被充分建模CNN/RNN类模型在…...
力扣Hot100(Java版本)
1. 哈希 1.1 两数之和 题目描述: 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同…...
Stream流简介、常用方法
Stream流的三类方法 获取Stream流 创建一条流水线,并把数据放到流水线上准备进行操作 中间方法 流水线上的操作一次操作完毕之后,还可以继续进行其他操作 终结方法 一个Stream流只能有一个终结方法是流水线上的最后一个操作 生成Stream流的方式 Collec…...
C# 集成 FastDFS 完整指南
1. 环境准备 (1) 安装 FastDFS 服务端 部署 Tracker 和 Storage 节点,确保服务正常运行。 配置 tracker_server 地址(如 192.168.1.100:22122)。 (2) 添加 NuGet 包 通过 NuGet 安装 FastDFS 客户端库: Install-Pack…...
重构门店网络:从“打补丁“到“造地基“的跨越
您是否遇到过这样的窘境? 新店开张要等一周,就为装根网线; 偏远地区门店三天两头断网,顾客排长队却结不了账; 总部想看实时数据,结果收到一堆乱码报错; 总部ERP系统升级,2000家门…...
TI的ADS1291代替芯片LH001-99
血管疾病严重威胁人类生命健康安全,随着人口老龄化进程的加快和社会压力等因素的增加,患病率正呈现逐年上升趋势,并且越来越年轻化。然而,心血管疾病大多由器官器质性病变引起,一旦患病很难完全康复,需要进…...
NPOI 操作 Word 文档
管理 NuGet 程序包 # word操作 NPOI# 图片操作 SkiaSharp Controller代码 using Microsoft.AspNetCore.Mvc; using NPOI.Util; using NPOI.XWPF.Model; using NPOI.XWPF.UserModel; using SkiaSharp;namespace WebApplication2.Controllers {[Route("api/Npoi/[action]…...
css3基于伸缩盒模型生成一个小案例
css3基于伸缩模型生成一个小案例 在前面学习了尚硅谷天禹老师的css3内容后,基于伸缩盒模型做的一个小案例,里面使用了 flex 布局,以及主轴切换,以及主轴平分等特性,分为使用css3 伸缩盒模型方式,已经传统的…...
精简大语言模型:用于定制语言模型的自适应知识蒸馏
Streamlining LLMs: Adaptive Knowledge Distillation for Tailored Language Models 发表:NAACL 2025 机构:德国人工智能研究中心 Abstract 诸如 GPT-4 和 LLaMA-3 等大型语言模型(LLMs)在多个行业展现出变革性的潜力…...
Rollup入门与进阶:为现代Web应用构建超小的打包文件
我们常常面临Webpack复杂配置或是Babel转译后的冗余代码,结果导致最终的包体积居高不下加载速度也变得异常缓慢,而在众多打包工具中Rollup作为一个轻量且高效的选择,正悄然改变着这一切,本文将带你深入了解这个令人惊艳的打包工具…...
博客系统技术需求文档(基于 Flask)
以下内容是AI基于要求生成的技术文档,仅供参考~ 🧱 一、系统架构设计概览 层级 内容 前端层 HTML Jinja2 模板引擎,集成 Markdown 编辑器、代码高亮 后端层 Flask 框架,RESTful 风格,Jinja2 渲染 数据库 SQLi…...
快速排序、归并排序、计数排序
文章目录 前言一、归并排序算法逻辑递归实现非递归实现 二、快速排序算法介绍递归实现非递归实现算法的一种优化—三路划分法 四、计数排序算法原理代码实现优劣分析 五、排序算法的性能比较总结 前言 本文介绍这三种非常强大的排序算法,每种算法都有各自的特点、不…...
python语言与地理处理note 2025/05/11
1. 函数定义必须要在调用之前 (1)正确示例: def test():print("what a wonderful world!")test() (2)错误示例: test() def test():print("what a wonderful world!") 会报错&…...
贪心算法:最小生成树
假设无向图为: A-B:1 A-C:3 B-C:1 B-D:4 C-D:1 C-E:5 D-E:6 一、使用Prim算法: public class Prim {//声明了两个静态常量,用于辅助 Prim 算法的实现private static final int V 5;//点数private static final int INF Integer.MA…...
免费 OCR 识别 + 批量处理!PDF 工具 提升办公效率
各位办公小能手们!今天给你们介绍一款超厉害的软件——PDF工具V2.2!我跟你们说,这玩意儿就像是PDF界的超级英雄,专门搞定PDF文件的编辑、转换、压缩这些事儿。 先说说它的核心功能哈。基础文档管理方面,它能把好几个PD…...
尼康VR镜头防抖模式NORMAL和ACTIVE的区别(私人笔记)
1. NORMAL 模式(常规模式) 适用场景:一般手持拍摄,比如人像、静物、风景或缓慢平移镜头(如水平追拍)等。工作特性: 补偿手抖引起的小幅度震动(比如手持时自然的不稳)&am…...
在scala中sparkSQL读入csv文件
以下是 Scala 中使用 Spark SQL 读取 CSV 文件的核心步骤和代码示例(纯文本): 1. 创建 SparkSession scala import org.apache.spark.sql.SparkSession val spark SparkSession.builder() .appName("Spark SQL Read CSV") …...
swift flask python ipad当电脑键盘 实现osu x键和z键 长按逻辑有问题 quart 11毫秒
键盘不行我5星都打不过,磁轴不在身边 127.0.0.1不行要用192.168哪个地址 from flask import Flask from pynput.keyboard import Controller from threading import Threadapp Flask(__name__) keyboard Controller()# 按下按键 app.route("/press_down/<…...
浅论3DGS溅射模型在VR眼镜上的应用
摆烂仙君小课堂开课了,本期将介绍如何手搓VR眼镜,并将随手拍的电影变成3D视频。 一、3DGS模型介绍 3D 高斯模型是基于高斯函数构建的用于描述三维空间中数据分布概率的模型,高斯函数在数学和物理领域有着广泛应用,其在 3D 情境下…...
React状态管理-对state进行保留和重置
相同位置的相同组件会使得 state 被保留下来 当你勾选或清空复选框的时候,计数器 state 并没有被重置。不管 isFancy 是 true 还是 false,根组件 App 返回的 div 的第一个子组件都是 <Counter />: 你可能以为当你勾选复选框的时候 st…...
嵌入式STM32学习——外部中断EXTI与NVIC的基础练习⭐
按键控制LED灯 按键控制LED的开发流程: 第一步:使能功能复用时钟 第二布,配置复用寄存器 第三步,配置中断屏蔽寄存器 固件库按键控制LED灯 外部中断EXTI结构体:typedef struct{uint32_t EXTI_Line; …...
git merge和git rebase
git merge和git rebase 在Git中merge和rebase都是git在管理整合分支的两种主要工具,但是他们的工作方式、提交历史影响和使用场景不同。 git merge 定义 将两个分支的提交历史合并,创建一个新的合并提交(merge commit)ÿ…...
我的MCP相关配置记录
1.VSCode的Cline中的MCP {"mcpServers": {"github.com/modelcontextprotocol/servers/tree/main/src/github": {"autoApprove": [],"disabled": false,"timeout": 60,"command": "cmd","args&quo…...
浅聊一下数据库的索引优化
背景 这里的索引说的是关系数据库(MSSQL)中的索引。 本篇不是纯技术性的内容,只是聊一次性能调优的经历,包含到一些粗浅的实现和验证手段,所以,大神忽略即可。 额…对了,笔者对数据库的优化手段…...
如何创建maven项目
1.IDEA 中创建 Maven 项目 步骤一:点击 File -> New -> Project,在弹出的窗口左侧选择 Maven,点击 Next: 步骤二:填写项目的 GroupId、ArtifactId、Version 等信息(这些对应 pom.xml 中的关键配置&am…...
LORA: LOW-RANK ADAPTATION OF LARGE LANGUAGE MODELS
一、引言 在自然语言处理领域,大规模预训练语言模型(LLMs)展现出强大的语言理解和生成能力。然而,将这些模型适配到多个下游任务时,传统微调方法面临诸多挑战。LoRA(Low-Rank Adaptation of Large Language Models)作为一种创新的微调技术,旨在解决这些问题,为大语言…...
Conda在powershell终端中无法使用conda activate命令
主要有以下原因: Windows PowerShell安全策略:默认情况下,PowerShell的执行策略设置为"Restricted",这会阻止运行脚本,包括conda的初始化脚本。调用方式不同:在PowerShell中,需要使用…...
MySQL索引底层数据结构与算法
1、索引的数据结构 1.1、二叉树 1.2、红黑树(二叉平衡树) 1.3、hash表 对key进行一次hash计算就可以定位出数据存储的位置 问题:hash冲突问题、仅满足和in的查找,不支持范围查找 1.4、B-tree 1.5、B tree 非叶子节点不存储data&…...
GOOSE 控制块参数gocbRef及goID有大小写要求
在 IEC 61850 标准中,GOOSE 控制块参数gocbRef和goID的大小写是严格区分的。这一结论基于以下多维度分析: 一、标准协议与配置文件的强制性 XML 语法的刚性约束 GOOSE 控制块的配置信息通过 SCL(Substation Configuration Languageÿ…...
重庆医科大学附属第二医院外科楼外挡墙自动化监测
1.项目概述 重庆医科大学附属第二医院,重医附二院,是集医疗、教学、科研、预防保健为一体的国家三级甲等综合医院。前身为始建于1892年的“重庆宽仁医院”。医院现有开放床位 1380张,年门诊量超过百万人次,年收治住院病人4.5万人…...
3.4 数字特征
本章系统讲解随机变量的数字特征理论,涵盖期望、方差、协方差与相关系数的核心计算与性质。以下从四个核心考点系统梳理知识体系: 考点一:期望(数学期望) 1. 离散型随机变量的数学期望 一维情形: E ( X …...
servlet-api
本次内容总结 1、再次学习Servlet的初始化方法 2、学习Servlet中的ServletContext和<context-param> 3、什么是业务层 4、IOC 5、过滤器 7、TransActionManager、ThreadLocal、OpenSessionInViewFilter 1、再次学习Servlet的初始化方法 1)Servlet生命周期&…...
NLTK进行文本分类和词性标注
《python ⾃然语⾔处理实战》学习笔记 NLTK 下载依赖 !pip install nltkimport nltk nltk.download(punkt_tab)分词(tokenize) from nltk.tokenize import word_tokenize from nltk.text import Textinput_str """Twinkle, twinkle, little star, How I won…...
电机控制储备知识学习(一) 电机驱动的本质分析以及与磁相关的使用场景
目录 电机控制储备知识学习(一)一、电机驱动的本质分析以及与磁相关的使用场景1)电机为什么能够旋转2)电磁原理的学习重要性 二、电磁学理论知识1)磁场基础知识2)反电动势的公式推导 附学习参考网址欢迎大家…...
华三路由器单臂路由配置
目录 1.实验目的1.1 掌握华三路由器单臂路由配置方法2.1 路由器连接交换机,交换机划分多个 VLAN,不同 VLAN 的 PC 通过路由器实现通信 配置步骤与命令解析1.配置交换机2.配置路由器验证配置3.1 配置交换机 VLAN3.1.1 创建 VLAN3.1.2 配置端口所属 VLAN3.…...
一键转换上百文件 Word 批量转 PDF 软件批量工具
各位办公族们,你们有没有被手动把Word一个个转成PDF给折腾得欲哭无泪过啊?我之前就因为这事忙得晕头转向,眼睛都快看瞎了!不过呢,后来我发现了专门为咱提升办公效率设计的Word批量转PDF软件,那简直就是办公…...
矫平机:工业精密矫正的全维度解析
作为现代制造业的核心设备之一,矫平机通过消除材料残余应力、提升平整度,持续推动着汽车、航空航天、新能源等领域的质量升级。本文基于最新行业动态与技术突破,从原理革新到智能化实践展开深度解析。 一、核心原理:力学与智能的深…...
网络安全-等级保护(等保) 2-3 GB/T 22240—2020《信息安全技术 网络安全等级保护定级指南》-2020-04-28发布【现行】
################################################################################ 在开始等级保护安全建设前,第一步需要知道要保护的是什么,要保护到什么程度,所以在开始等级保护中介绍的第一个标准是《定级指南》,其中明确了…...
GNSS数据自动化下载系统的设计与实现
摘要 本文详细介绍了三种不同设计的GNSS数据自动化下载系统,分别针对IGS观测数据、GRACE-FO Level-1B数据以及通过代理服务器获取数据的需求场景。系统采用Python实现,具备断点续传、完整性校验、异常处理和进度显示等核心功能。实验结果表明࿰…...
c语言第一个小游戏:贪吃蛇小游戏06
实现贪吃蛇四方向的风骚走位 实现代码 #include <curses.h> #include <stdlib.h> struct snake{ int hang; int lie; struct snake *next; }; struct snake *head; struct snake *tail; int key; int dir; //全局变量 #define UP 1 //这个是宏定义&a…...
人工智能_大模型数据标注主要做什么_拉框_人工智能训练师_数据标准师介绍---人工智能工作笔记0244
随着大模型的快速发展,数据标注迅速成为比较热门的工作,那么 数据标注,具体干什么呢? 因为现在人工智能在某个领域如果理解,或者识别的越精准,那么 就需要越高质量的数据, 就是因为,模型的训练,大多还是有监督深度学习.给他足够高质量的数据才行有好的效果. 可以看到在AI领…...