每天一道leetcode:797. 所有可能的路径(图论中等深度优先遍历)
今日份题目:
给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。
示例1

输入:graph = [[1,2],[3],[3],[]] 输出:[[0,1,3],[0,2,3]] 解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例2

输入:graph = [[4,3,1],[3,2,4],[3],[4],[]] 输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
提示
-
n == graph.length -
2 <= n <= 15 -
0 <= graph[i][j] < n -
graph[i][j] != i(即不存在自环) -
graph[i]中的所有元素 互不相同 -
保证输入为 有向无环图(DAG)
题目思路
使用深度优先遍历,用p数组记录路径。递归遍历结束条件就是到达结尾,所以需要一个int数据记录当前所在位置,如果到结尾了就返回。
代码
class Solution
{
public:vector<vector<int>> ans;vector<int> p;void dfs(vector<vector<int>>& graph, int x, int n) { //x用来标记当前所在位置,n标记结尾所在位置if(x==n) //到结尾了,返回{ans.push_back(p);return;}for(auto& y:graph[x]) //遍历临界节点{p.push_back(y);dfs(graph,y,n);p.pop_back();//还原队列,确保其他dfs操作的正确进行}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {p.push_back(0);dfs(graph,0,graph.size()-1);return ans;}
};
提交结果

欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:
每天一道leetcode:797. 所有可能的路径(图论中等深度优先遍历)
今日份题目: 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序) graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节…...
创建预留成本中心与指定工厂不一致
创建预留成本中心与指定工厂不一致 这种情况SAP会警告提示,可以强制通过。 如果公司不允许跨公司领料,可以将消息号 M7517的类型从W改为为E tcode:OMCQ SPRO->物料管理->库存管理和实际库存->定义系统消息的属性->系统信息设置...
SCF金融公链新加坡启动会 创新驱动未来
新加坡迎来一场引人瞩目的金融科技盛会,SCF金融公链启动会于2023年8月13日盛大举行。这一受瞩目的活动将为金融科技领域注入新的活力,并为广大投资者、合作伙伴以及关注区块链发展的人士提供一个难得的交流平台。 在SCF金融公链启动会上, Wil…...
希尔排序【Java算法】
文章目录 1. 概念2. 思路3. 代码实现 1. 概念 希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分…...
互联网发展历程:从布线到无线,AC/AP的崭新时代
互联网的发展,一直在追求更便捷、更灵活的连接方式。在网络的早期,布线问题常常让人头疼。一项革命性的技术应运而生,那就是“无线AC/AP”。 布线问题的烦恼:繁琐的布线 早期网络的布线工作常常耗费时间和精力,尤其在大…...
Vue3 Axios网络请求简单应用
cd 到项目 安装Axios:cnpm install --save axios post传递参数 需要安装querystring 用于转换参数格式:cnpm install --save querystring 运行示例: 后台接口: GetTestData.java package com.csdnts.api;import java.io.IOExce…...
day-18 代码随想录算法训练营(19)二叉树 part05
513.找树左下角的值 思路一:层序遍历,每一层判断是不是最后一层,是的话直接返回第一个; 如何判断是不是最后一层呢,首先队列头部,其次记录左右子节点都没有的节点数是不是等于que.size();或…...
【数据结构OJ题】移除链表元素
原题链接:https://leetcode.cn/problems/remove-linked-list-elements/description/ 1. 题目描述 2. 思路分析 我们可以定义一个结构体指针变量cur,让cur一开始指向头结点,同时定义一个结构体指针prev,令prev初始化为空指针NULL…...
centos 安装 virtualbox
参考 https://phoenixnap.com/kb/how-to-install-virtualbox-centos-7 遇到 Gpg Keys Failue 这样解决 将 rpm 包下载到本地 –disablerepovirtualbox sudo yum --disablerepovirtualbox localinstall VirtualBox-7.0-7.0.10_158379_el7-1.x86_64 failure: repodata/repomd…...
Java8之Optional类的基本使用
文章目录 一、简介二、常见的Optional用法:1、创建Optional对象:1.1 使用of()方法:1.2 使用ofNullable()方法:1.3 使用empty()方法: 2、判断Optional是否包含值:2.1 使用isPresent()方法: 3、获…...
LinuxPTP时间同步
参考文献: http://linuxptp.sourceforge.net/ 0、硬件支持 查看网卡是否支持软硬件时间戳: sudo ethtool -T eno1 Time stamping parameters for eno1: Time stamping parameters for eno1: Capabilities: hardware-transmit (SOF_TIMESTAMPIN…...
【Django】Task1安装python环境及运行项目
【Django】Task1安装python环境及运行项目 写在最前 8月份Datawhale组队学习,在这个群除我佬的时代,写一下blog记录学习过程。 参考资源: 学习项目github:https://github.com/Joe-2002/sweettalk-django4.2 队长博客:…...
00 - 环境配置
查看所有文章链接:(更新中)GIT常用场景- 目录 文章目录 1. 环境说明2. 安装配置2.1 配置user信息2.2 config的三个作用域 3. 建git仓库3.1 把已有的项目代码纳入git管理3.2 新建的项目直接用git管理3.3 配置local的user和email3.4 优先级&…...
R语言实现计算净重新分类指数(NRI)和综合判别改善指数(IDI)
两个模型比较,与第一个模型相比,NRI(重新分对的 - 重新分错的)/总人数。IDI(新模型患者平均预测概率-旧模型患者平均预测概率)-(新模型非患者平均预测概率-旧模型非患者平均预测概率)…...
【面试总结】八股①
目录 数据库缓存穿透是什么常见的sql调优方法有哪些使用表的别名为什么能优化查询性能MySQL事务特性是哪些事务隔离级别有哪些 Java基础StringBuffer和StringBuilder的区别String直接引号新建和new String新建的区别Java中继承和实现的各种关系 消息队列Redis计算机常识缓冲击穿…...
AI绘画 | 一文学会Midjourney绘画,创作自己的AI作品(快速入门+参数介绍)
一、生成第一个AI图片 首先,生成将中文描述词翻译成英文 然后在输入端输入:/imagine prompt:Bravely running boy in Q version, cute head portrait 最后,稍等一会即可输出效果 说明: 下面的U1、U2、U3、U4代表的第一张、第二张…...
MongoDB 数据库详细介绍
MongoDB 数据库详细介绍 MongoDB(来自“Humongous”,意为巨大的)是一个开源、高性能、无模式(NoSQL)、文档导向的分布式数据库。它以其灵活性、可扩展性和强大的查询功能而闻名于世。MongoDB 使用 JSON 格式的文档来存…...
Qt在mac安装
先在app store下载好Xcode 打开Xcode 随便建个文件给它取个名字找个地方放提醒没建立git link,不用理他打开终端, 输入/usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"...
STM32 F103C8T6学习笔记1:开发环境与原理图的熟悉
作为一名大学生,学习单片机有一段时间了,也接触过嵌入式ARM的开发,但从未使用以及接触过STM32C8T6大开发使用,于是从今日开始,将学习使用它~ 本文介绍STM32C8T6最小系统开发环境搭建注意问题,STM32C8T6单片…...
【Linux命令详解 | ps命令】 ps命令用于显示当前系统中运行的进程列表,帮助监控系统状态。
文章标题 简介一,参数列表二,使用介绍1. 基本用法2. 显示所有进程3. 显示进程详细信息4. 根据CPU使用率排序5. 查找特定进程6. 显示特定用户的进程7. 显示进程内存占用8. 查看进程树9. 实时监控进程10. 查看特定进程的详细信息11. 查看特定用户的进程统计…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
【若依】框架项目部署笔记
参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作: 压缩包下载:http://download.redis.io/releases 1. 上传压缩包,并进入压缩包所在目录,解压到目标…...
MyBatis-Plus 常用条件构造方法
1.常用条件方法 方法 说明eq等于 ne不等于 <>gt大于 >ge大于等于 >lt小于 <le小于等于 <betweenBETWEEN 值1 AND 值2notBetweenNOT BETWEEN 值1 AND 值2likeLIKE %值%notLikeNOT LIKE %值%likeLeftLIKE %值likeRightLIKE 值%isNull字段 IS NULLisNotNull字段…...
汇编语言学习(三)——DoxBox中debug的使用
目录 一、安装DoxBox,并下载汇编工具(MASM文件) 二、debug是什么 三、debug中的命令 一、安装DoxBox,并下载汇编工具(MASM文件) 链接: https://pan.baidu.com/s/1IbyJj-JIkl_oMOJmkKiaGQ?pw…...
电脑定时关机工具推荐
软件介绍 本文介绍一款轻量级的电脑自动关机工具,无需安装,使用简单,可满足定时关机需求。 工具简介 这款关机助手是一款无需安装的小型软件,文件体积仅60KB,下载后可直接运行,无需复杂配置。 使用…...
