[100天算法】-面试题 04.01.节点间通路(day 72)

news/2024/2/28 11:20:16

题目描述

节点间通路。给定有向图,设计一个算法,找出两个节点之间是否存在一条路径。示例1:输入:n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
输出:true
示例2:输入:n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
输出 true
提示:节点数量n在[0, 1e5]范围内。
节点编号大于等于 0 小于 n。
图中可能存在自环和平行边。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/route-between-nodes-lcci
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法 1:图+DFS

思路

简单学习了下图,笔记。

  1. 建一个邻接表
  2. dfs 查找

邻接表

dfs 伪代码

如果当前顶点就是目标顶点:return true
否则:把当前顶点加入“已遍历”队列中let found = false 记录dfs邻接点是否能找到目标顶点遍历当前顶点的所有邻接点:如果这个邻接点是“未遍历”:继续dfs查找,只要有一个查找返回了true,found = truereturn found

代码

JavaScript Code

/*** @param {number} n* @param {number[][]} graph* @param {number} start* @param {number} target* @return {boolean}*/
var findWhetherExistsPath = function (n, graph, start, target) {// 建图const adjList = {};for (let i = 0; i < n; i++) {adjList[i] = new Set();}graph.forEach(edge => adjList[edge[0]].add(edge[1]));// dfsconst dfs = (start, target, adjList, visited) => {if (start === target) return true;visited[start] = true;const neighs = adjList[start];let found = false;neighs.forEach(neigh => {if (!visited[neigh]) {const res = dfs(neigh, target, adjList, visited);res && (found = res);}});return found;};return dfs(start, target, adjList, []);
};

复杂度分析

  • 时间复杂度:$O(V+E)$,V 是顶点数,E 是边的数量。
  • 空间复杂度:$O(V+E)$,V 是顶点数,E 是边的数量,邻接表的空间复杂度是 O(V+E),dfs 递归栈的空间复杂度是 O(V)。

http://www.ppmy.cn/news/1211764.html

相关文章

C++ 同构字符串/ 单词规律

给定两个字符串 s 和 t &#xff0c;判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t &#xff0c;那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符&#xff0c;同时不改变字符的顺序。不同字符不能映射到同一个字符上&#xff0c;相…

男科医院服务预约小程序的作用是什么

医院的需求度从来都很高&#xff0c;随着技术发展&#xff0c;不少科目随之衍生出新的医院的&#xff0c;比如男科医院、妇科医院等&#xff0c;这使得目标群体更加精准&#xff0c;同时也赋能用户可以快速享受到服务。 当然相应的男科医院在实际经营中也面临痛点&#xff1a;…

基于PHP的设云尘资讯网站设计与实现

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下&#xff0c;你想解决的问…

​软考-高级-系统架构设计师教程(清华第2版)【第2章 计算机系统基础知识-思维导图】​

软考-高级-系统架构设计师教程&#xff08;清华第2版&#xff09;【第2章 计算机系统基础知识-思维导图】 课本里章节里所有蓝色字体的思维导图

2023.11.11 关于 Spring 中 Bean 的作用域

目录 Bean 的作用域 作用域的定义 Singleton&#xff08;单例作用域&#xff09; Prototype&#xff08;原型作用域&#xff09; Request&#xff08;请求作用域&#xff09; Session&#xff08;会话请求&#xff09; Application&#xff08;全局作用域&#xff09; …

吴恩达《机器学习》8-1->8-2:非线性假设、神经元和大脑

一、非线性假设 在之前学到的线性回归和逻辑回归中&#xff0c;存在一个缺点&#xff0c;即当特征数量很多时&#xff0c;计算的负荷会变得非常大。考虑一个例子&#xff0c;假设我们使用 &#x1d465;₁, &#x1d465;₂ 的多项式进行预测&#xff0c;这时我们可以很好地应…

单源最短路的建图方式 , 1129. 热浪,模板题

1129. 热浪 - AcWing题库 德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪&#xff01;&#xff01;&#xff01; 他们的德克萨斯长角牛吃起来不错&#xff0c;可是它们并不是很擅长生产富含奶油的乳制品。 农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶…

【从0到1设计一个网关】性能优化---使用Disruptor提供缓冲区

文章目录 什么是缓冲区队列Disruptor高性能的原因Disruptor实战注:学习这篇文章之前推荐先对Disruptor的使用有了解,否则我的代码中即使有非常详细的注释你也并不能理解这些注释的作用,以及为什么我要需要这样子编写代码。 同时,这将会是网关系列最后一篇文章,由于文章写的…

Vue3 源码解读系列(四)——组件更新

组件更新 组件更新流程&#xff1a; 从头部开始同步 从尾部开始同步 挂载剩余的新节点 删除多余的旧节点 处理未知的子序列 当两个节点类型相同时&#xff0c;执行更新操作当新子节点中没有旧子节点中的某些节点时&#xff0c;执行删除操作当新子节点中多了旧子节点中没有…

学习c#的第六天

目录 C# 判断 if 语句 嵌套 if 语句 switch 语句 嵌套 switch 语句 ? : 运算符 C# 循环 循环类型 while 循环 for/foreach 循环 do...while 循环 嵌套循环 循环控制语句 break 语句 continue 语句 无限循环 C# 判断 if 语句 在C#中&#xff0c;if语句用于根…

数据结构之双向链表

目录 引言 链表的分类 双向链表的结构 双向链表的实现 定义 创建新节点 初始化 打印 尾插 头插 判断链表是否为空 尾删 头删 查找与修改 指定插入 指定删除 销毁 顺序表和双向链表的优缺点分析 源代码 dlist.h dlist.c test.c 引言 数据结构…

YOLOv8-Seg改进:分割注意力系列篇 | 高效多尺度注意力 EMA | ICASSP2023

🚀🚀🚀本文改进:EMA跨空间学习高效多尺度注意力引入到YOLOv8中进行二次创新,改进方法1)head层输出层结合;2)加入backbone; 🚀🚀🚀EMAAttention 亲测在多个数据集能够实现涨点,同样适用于小目标分割 🚀🚀🚀YOLOv8-seg创新专栏:http://t.csdnimg.cn/…

Rust逆向学习 (5)

文章目录 Reverse for Vecvec! 与 添加元素元素访问元素遍历枚举数组弹出最后一个元素——pop 总结 本文将对Rust中的通用集合类型——动态数组 Vec进行学习&#xff0c;对应参考书中的第8章。 Reverse for Vec Vec是Rust中的动态数据结构&#xff0c;与C中的vector功能类似。…

生信工具 | 测序数据质控与过滤 - fqtrim

fqtrim trimming&filtering of next-gen reads fqtrim 是一个多功能的独立实用程序&#xff0c;可用于去除高通量测序仪产出的测序数据接头&#xff0c;poly-A 尾&#xff0c;末端未知碱基&#xff08;Ns&#xff09;和低质量 3 区域。该程序允许接头序列和 poly-A 序列的不…

怎么实现this对象的深拷贝?

要实现this对象的深拷贝&#xff0c;你可以使用一些常见的深拷贝技术&#xff0c;例如递归复制或使用JSON.parse()和JSON.stringify()方法。下面是两种常见的方法&#xff1a; 1&#xff1a;递归复制&#xff1a; function deepCopy(obj) {if (typeof obj ! object || obj n…

Easyui DataGrid combobox联动下拉框内容

发票信息下拉框联动&#xff0c;更具不同的发票类型&#xff0c;显示不同的税率 专票 普票 下拉框选择事件 function onSelectType(rec){//选中值if (rec2){//普通发票对应税率pmsPlanList.pmsInvoiceTaxRatepmsPlanList.pmsInvoiceTaxRateT}else {//专用发票对应税率pmsPlan…

基于ssm的高校失物招领管理系统

基于ssm的高校失物招领管理系统 摘要 失物招领管理系统是一种利用现代信息技术&#xff0c;为高校提供高效、便捷的失物招领服务的平台。本系统基于SSM框架&#xff08;Spring SpringMVC MyBatis&#xff09;&#xff0c;充分利用了各框架的优势&#xff0c;实现了系统的稳定…

Redis之哨兵模式

文章目录 前言什么是哨兵模式&#xff1f;1.概述2.作用3.测试4.优点5.缺点6.哨兵模式的全部配置 总结 前言 哨兵模式说白点就是&#xff1a;自动选举老大的模式。 什么是哨兵模式&#xff1f; 1.概述 主从切换技术的方法是∶当主服务器宕机后&#xff0c;需要手动把一台从服…

kubeadm部署k8s及高可用

目录 CNI 网络组件 1、flannel的功能 2、flannel的三种模式 3、flannel的UDP模式工作原理 4、flannel的VXLAN模式工作原理 5、Calico主要组成部分 6、calico的IPIP模式工作原理 7、calico的BGP模式工作原理 8、flannel 和 calico 的区别 Kubeadm部署k8s及高可用 1、…

使用大型语言模型进行文本摘要

路易斯费尔南多托雷斯 &#x1f4dd; Text Summarization with Large Language Models。通过单击链接&#xff0c;您将能够逐步阅读完整的过程&#xff0c;并与图进行交互。谢谢你&#xff01; 一、介绍 2022 年 11 月 30 日&#xff0c;标志着机器学习历史上的重要篇章。就在这…
最新文章