【LeetCode】公交路线 [H](宽度优先遍历)
815. 公交路线 - 力扣(LeetCode)
一、题目
给你一个数组 routes ,表示一系列公交线路,其中每个 routes[i] 表示一条公交线路,第 i 辆公交车将会在上面循环行驶。
例如,路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发(初始时不在公交车上),要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站,返回 -1 。
示例 1:
输入:routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出:2
解释:最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2:
输入:routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出:-1
提示:
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= 105
- routes[i] 中的所有值 互不相同
- sum(routes[i].length) <= 105
- 0 <= routes[i][j] < 106
- 0 <= source, target < 106
二、代码
class Solution {// routes数组表示每一种公交线路包括哪些公交站// 0 : [1,3,7,0] 0号公交线路包括1、3、7、0这四个公交站// 1 : [7,9,6,2]// ....// 返回:返回换乘次数+1 -> 返回一共坐了多少次公交。public int numBusesToDestination(int[][] routes, int source, int target) {// 如果起点和目标一致,直接返回0if (source == target) {return 0;}// 全部的公交线路数int n = routes.length;// key : 车站// value : list -> 该车站被哪些线路拥有 list中存储的公交线路编号HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();// 根据routes数组构造出mapfor (int i = 0; i < n; i++) {// 遍历每一条路线下的每一个车站for (int station : routes[i]) {// 将每一个车站所在的线路编号加入到map中这个车站对应的value中// 如果这个车站还没有创建map,就手动创建一个if (!map.containsKey(station)) {map.put(station, new ArrayList<Integer>());}// station车站被i号路线拥有map.get(station).add(i);}}// 至此,通过map就可以快速取出一个车站可以通往哪些公交路线// 宽度优先遍历用的队列,里面加入的是公交线路编号ArrayList<Integer> queue = new ArrayList<>();// 标记路线是否已经被宽度优先遍历过了boolean[] set = new boolean[n];// 将起点能够走到的公交线路都取出来,这些公交线路就是我们一开始能走的路线for (int route : map.get(source)) {// 将公交线路加入到队列中queue.add(route);// 将这个线路标记为true,表示已经遍历到了set[route] = true;}// 记录换乘次数int cnt = 0;// 开始深度优先遍历,每次就直接把一层的都遍历出来while (!queue.isEmpty()) {// 记录下一层宽度遍历的路线列表ArrayList<Integer> nextRoutes = new ArrayList<>();// 遍历当前队列中的所有线路,表示当前能走到的线路for (Integer route : queue) {// 获取这些线路包括车站int[] stations = routes[route];// 遍历每一条线路的所有车站for (int station : stations) {// 如果这个车站就是终点,直接返回换乘次数+1if (station == target) {// 之所以加1,是因为cnt统计的是换乘次数,题目要求要返回乘坐公交车的数量,所以要加1return cnt + 1;}// 通过这个车站再去找下一次换乘能走到的路线由哪些。利用之前构造的map结构找for (int nextRoute : map.get(station)) {// 保证这个路线没有被遍历过if (!set[nextRoute]) {// 将这个路线加入到nextRoutes中,供下一层遍历使用nextRoutes.add(nextRoute);// 将这个路线标记为已经遍历到了set[nextRoute] = true;}}}}// 每遍历一层,换成次数就加1cnt++;// 将下一层的路线列表赋值给queue,作为下一轮遍历过程中可以走到的路线列表queue = nextRoutes;}// 不能走到就返回-1return -1;}
}
三、解题思路
先把每个站点拥有哪些线路标好,这个线路就是指的routes[i]数组的下标,把每个站点和一个数字i绑定,那么就可以通过这个数字i,直接找到routes[i],这个就是这个站点所在的线路。
从source出发,先遍历source这个站点的所有所在路线,也就遍历出了第一层1、2、3这三条路线,表示source这个站点,下一步可以走到1、2、3这三条公交线路中(公交线路本身也是包含了多个站点的),我们也就知道了从source这个点,只换乘一次能到达的全新的线路有哪些,将这些路线加入到队列中,并且再去遍历一下这三条线路所经过的所有车站,就能够得到只换乘一次,能到达的所有车站有哪些,再通过这些车站,去找下一次换乘能到达的路线有哪些,将这些新路线存储到nextRoute数组中,供下一层宽度遍历时使用。
在宽度优先遍历过程中,每遍历一层,也就是换成次数加1,因为每一层的遍历就是从一个站点到另外的线路上,期间就是只需要换乘一次。两条线路虽然都有多个站点,但是只有两辆不同的车而已。
遍历完第一层后,下一层的宽度优先遍历就是在用相同的方法,以nextRoute数组中上一轮换乘一次可以来到的全新路线为起点,再遍历一下每一个路线只换乘一次就能到达的全新线路,然后再去看这些全新线路都能经过的车站都找出来,通过这些车站再去找下一轮换乘一次能到达的全新路线有哪些,存储到nextRoute数组中,在下层的遍历时就会将这些一次换乘就能走到的全新路线加入到队列中。整个流程就是每一次都直接把一整层遍历出来,完成深度优先遍历。
因为每次都是向外扩一层,按照宽度优先遍历的顺序来遍历,所以只要是在这个过程中找到了目的地target站点,那么记录的换乘次数一定是最少的。
相关文章:
【LeetCode】公交路线 [H](宽度优先遍历)
815. 公交路线 - 力扣(LeetCode) 一、题目 给你一个数组 routes ,表示一系列公交线路,其中每个 routes[i] 表示一条公交线路,第 i 辆公交车将会在上面循环行驶。 例如,路线 routes[0] [1, 5, 7] 表示第 …...

报表生成器 FastReport .Net 用户指南 2023(十):Band的属性
FastReport .Net是一款全功能的Windows Forms、ASP.NET和MVC报表分析解决方案,使用FastReport .NET可以创建独立于应用程序的.NET报表,同时FastReport .Net支持中文、英语等14种语言,可以让你的产品保证真正的国际性。 FastReport.NET官方版…...

DAMA数据管理知识体系指南之文档和内容管理
第10章 文档和内容管理 10.1 简介 文档和内容管理是对存储在关系数据库以外的信息的采集、存储、访问以及使用的控制活动。文档和内容管理的侧重点在完整性和访问控制上。因此,它与关系数据库的数据操作管理大致相同。由于多数非结构化数据与存储在结构化文件中的…...
C++入门:数据结构
C/C 数组允许定义可存储相同类型数据项的变量,但是结构是 C 中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。结构用于表示一条记录,假设您想要跟踪图书馆中书本的动态,您可能需要跟踪每本书的下列属性&#x…...

C语言实现烟花表白,内含源码!!
虽然现在看烟花有一定难度,但代码式烟花可以随时随地看! 烟花的代码很多,实际上是可以用 Python、HTML5 等语言写烟花,但今天主要想和大家分享用C语言写的烟花代码,非常细致和实用。 同学们一定要亲自敲一遍…...

虚拟机安装CentOS 7(带界面)
目录 一、虚拟机安装CentOS 7(带界面) 1、打开下好的VMware,点击创建虚拟机 2、下一步 3、点击下一步 4、选择Linux,ContOS7,点击下一步 5、修改虚拟机名称和路径 6、下一步 7、点击自定义硬件 8、设置虚拟机大…...

Java测试——selenium具体操作
selenium的前置准备工作可以参考我之前的博客:Java测试——selenium的安装与使用教程 这篇博客讲解一下selenium的常见操作 先创建driver ChromeDriver driver new ChromeDriver();输入网址 driver.get("https://www.baidu.com");常见操作 查找元素…...

电子器件系列32:逻辑与门芯片74LS11
一、编码规则 先看看这个代码的意思:74LS11 74是一个系列(74 表示为工作温度范围,74: 0 ~ 70度。) ls的意思就是工艺类型(Bipolar(双极)工艺) 11是代码 什么是74系列逻辑芯片? - 知乎 什么是…...

LeetCode-101. 对称二叉树
目录题目分析递归法题目来源 101. 对称二叉树 题目分析 首先想清楚,判断对称二叉树要比较的是哪两个节点,要比较的可不是左右节点! 对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一…...
使用intlinprog求解指派问题MATLAB代码分享
% 输入指派矩阵C [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10];f C(:); %生成一个列向量,作为目标函数系数,matlab默认以列排序[m,n] size(C);Aeq zeros(2*n,n*n); %2*n个等式约束,n*n个变量for i 1:n %这里先生成的是后5个…...

Spark On YARN时指定Python版本
坑很多,直接上兼容性最佳的命令,将python包上传到hdfs或者file:/home/xx/(此处无多余的/) # client 模式 $SPARK_HOME/spark-submit \ --master yarn \ --deploy-mode client \ --num-executors 2 \ --conf "spark.yarn.dist.archives<Python包…...
[数据库]库的增删改查
●🧑个人主页:你帅你先说. ●📃欢迎点赞👍关注💡收藏💖 ●📖既选择了远方,便只顾风雨兼程。 ●🤟欢迎大家有问题随时私信我! ●🧐版权:本文由[你帅…...

Wine零知识学习1 —— 介绍
一、什么是Wine Wine是“Wine Is Not an Emulator” 的首字母缩写,是一个能够在多种POSIX-compliant操作系统(诸如Linux、macOS及BSD等)上运行 Windows 应用的兼容层。Wine不像虚拟机或者模拟器那样模仿内部的Windows逻辑,而是將…...

设计模式--建造者模式 builder
设计模式--建造者模式 builder)建造者模式简介建造者模式--小例子(电脑购买)1.产品类2.抽象构建者3.实体构建类4.指导者类5.客户端测试类小结建造者模式简介 建造者模式有四个角色,概念划分如下: Product : 产品类&a…...

终于周末啦,继续来总结一下Python的一些知识点啦
目录 Python概念梳理 常见概念梳理 Python经典判断题 判断题 选择题 Python概念梳理 常见概念梳理 Python中,不仅仅变量的值是可以变化的,类型也是可以随时变化的 1、Python的变量必须初始化否则提示 is not defined 2、if、while中定义的变量在…...

CUDA By Example(八)——流
文章目录页锁定主机内存可分页内存函数页锁定内存函数CUDA流使用单个CUDA流使用多个CUDA流GPU的工作调度机制高效地使用多个CUDA流遇到的问题(未解决)页锁定主机内存 在之前的各个示例中,都是通过 cudaMalloc() 在GPU上分配内存,以及通过标准的C库函数 …...

02- pandas 数据库 (数据库)
pandas 数据库重点: pandas 的主要数据结构: Series (一维数据)与 DataFrame (二维数据)。 pd.DataFrame(data np.random.randint(0,151,size (5,3)), # 生成pandas数据 index [Danial,Brandon,softpo,Ella,Cindy], # 行索引 …...
less常用语法总结
CSS预处理器 CSS 预处理器是什么?一般来说,它们基于 CSS 扩展了一套属于自己的 DSL,来解决我们书写 CSS 时难以解决的问题: 语法不够强大,比如无法嵌套书写导致模块化开发中需要书写很多重复的选择器;没有变量和合理的样式复用机制,使得逻辑上相关的属性值必须以字面量…...

DHCP Relay中继实验
DHCP Relay实验拓扑图设备配置结果验证拓扑图 要求PC1按照地址池自动分配,而PC要求分配固定的地址,网段信息已经在图中进行标明。 设备配置 AR1: AR1作为DHCP Server基本配置跟DHCP Server没区别,不过要加一条静态路由ÿ…...

“1+1>2”!《我要投资》与天际汽车再度“双向奔赴”!
文|螳螂观察 作者| 图霖 胡海泉老师重磅回归、创始人现场真情告白……新一季的《我要投资》,不仅维持了往季在专业度上的高水准,也贡献了不少高话题度的“出圈”时刻。 在竞争激烈的的综艺节目竞技场,能举办数季的节目,往往都是…...

51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...