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

每天一道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. 所有可能的路径(图论中等深度优先遍历)

今日份题目&#xff1a; 给你一个有 n 个节点的 有向无环图&#xff08;DAG&#xff09;&#xff0c;请你找出所有从节点 0 到节点 n-1 的路径并输出&#xff08;不要求按特定顺序&#xff09; graph[i] 是一个从节点 i 可以访问的所有节点的列表&#xff08;即从节点 i 到节…...

创建预留成本中心与指定工厂不一致

创建预留成本中心与指定工厂不一致 这种情况SAP会警告提示&#xff0c;可以强制通过。 如果公司不允许跨公司领料&#xff0c;可以将消息号 M7517的类型从W改为为E tcode&#xff1a;OMCQ SPRO->物料管理->库存管理和实际库存->定义系统消息的属性->系统信息设置...

SCF金融公链新加坡启动会 创新驱动未来

新加坡迎来一场引人瞩目的金融科技盛会&#xff0c;SCF金融公链启动会于2023年8月13日盛大举行。这一受瞩目的活动将为金融科技领域注入新的活力&#xff0c;并为广大投资者、合作伙伴以及关注区块链发展的人士提供一个难得的交流平台。 在SCF金融公链启动会上&#xff0c; Wil…...

希尔排序【Java算法】

文章目录 1. 概念2. 思路3. 代码实现 1. 概念 希尔排序也是一种插入排序&#xff0c;它是简单插入排序经过改进之后的一个更高效的版本&#xff0c;也称为缩小增量排序。希尔排序在数组中采用跳跃式分组的策略&#xff0c;通过某个增量将数组元素划分为若干组&#xff0c;然后分…...

互联网发展历程:从布线到无线,AC/AP的崭新时代

互联网的发展&#xff0c;一直在追求更便捷、更灵活的连接方式。在网络的早期&#xff0c;布线问题常常让人头疼。一项革命性的技术应运而生&#xff0c;那就是“无线AC/AP”。 布线问题的烦恼&#xff1a;繁琐的布线 早期网络的布线工作常常耗费时间和精力&#xff0c;尤其在大…...

Vue3 Axios网络请求简单应用

cd 到项目 安装Axios&#xff1a;cnpm install --save axios post传递参数 需要安装querystring 用于转换参数格式&#xff1a;cnpm install --save querystring 运行示例&#xff1a; 后台接口&#xff1a; GetTestData.java package com.csdnts.api;import java.io.IOExce…...

day-18 代码随想录算法训练营(19)二叉树 part05

513.找树左下角的值 思路一&#xff1a;层序遍历&#xff0c;每一层判断是不是最后一层&#xff0c;是的话直接返回第一个; 如何判断是不是最后一层呢&#xff0c;首先队列头部&#xff0c;其次记录左右子节点都没有的节点数是不是等于que.size()&#xff1b;或…...

【数据结构OJ题】移除链表元素

原题链接&#xff1a;https://leetcode.cn/problems/remove-linked-list-elements/description/ 1. 题目描述 2. 思路分析 我们可以定义一个结构体指针变量cur&#xff0c;让cur一开始指向头结点&#xff0c;同时定义一个结构体指针prev&#xff0c;令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用法&#xff1a;1、创建Optional对象&#xff1a;1.1 使用of()方法&#xff1a;1.2 使用ofNullable()方法&#xff1a;1.3 使用empty()方法&#xff1a; 2、判断Optional是否包含值&#xff1a;2.1 使用isPresent()方法&#xff1a; 3、获…...

LinuxPTP时间同步

参考文献&#xff1a; http://linuxptp.sourceforge.net/ 0、硬件支持 查看网卡是否支持软硬件时间戳&#xff1a; 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组队学习&#xff0c;在这个群除我佬的时代&#xff0c;写一下blog记录学习过程。 参考资源&#xff1a; 学习项目github&#xff1a;https://github.com/Joe-2002/sweettalk-django4.2 队长博客&#xff1a…...

00 - 环境配置

查看所有文章链接&#xff1a;&#xff08;更新中&#xff09;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)

两个模型比较&#xff0c;与第一个模型相比&#xff0c;NRI&#xff08;重新分对的 - 重新分错的&#xff09;/总人数。IDI&#xff08;新模型患者平均预测概率-旧模型患者平均预测概率&#xff09;-&#xff08;新模型非患者平均预测概率-旧模型非患者平均预测概率&#xff09…...

【面试总结】八股①

目录 数据库缓存穿透是什么常见的sql调优方法有哪些使用表的别名为什么能优化查询性能MySQL事务特性是哪些事务隔离级别有哪些 Java基础StringBuffer和StringBuilder的区别String直接引号新建和new String新建的区别Java中继承和实现的各种关系 消息队列Redis计算机常识缓冲击穿…...

AI绘画 | 一文学会Midjourney绘画,创作自己的AI作品(快速入门+参数介绍)

一、生成第一个AI图片 首先&#xff0c;生成将中文描述词翻译成英文 然后在输入端输入&#xff1a;/imagine prompt:Bravely running boy in Q version, cute head portrait 最后&#xff0c;稍等一会即可输出效果 说明&#xff1a; 下面的U1、U2、U3、U4代表的第一张、第二张…...

MongoDB 数据库详细介绍

MongoDB 数据库详细介绍 MongoDB&#xff08;来自“Humongous”&#xff0c;意为巨大的&#xff09;是一个开源、高性能、无模式&#xff08;NoSQL&#xff09;、文档导向的分布式数据库。它以其灵活性、可扩展性和强大的查询功能而闻名于世。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:开发环境与原理图的熟悉

作为一名大学生&#xff0c;学习单片机有一段时间了&#xff0c;也接触过嵌入式ARM的开发&#xff0c;但从未使用以及接触过STM32C8T6大开发使用&#xff0c;于是从今日开始&#xff0c;将学习使用它~ 本文介绍STM32C8T6最小系统开发环境搭建注意问题&#xff0c;STM32C8T6单片…...

【Linux命令详解 | ps命令】 ps命令用于显示当前系统中运行的进程列表,帮助监控系统状态。

文章标题 简介一&#xff0c;参数列表二&#xff0c;使用介绍1. 基本用法2. 显示所有进程3. 显示进程详细信息4. 根据CPU使用率排序5. 查找特定进程6. 显示特定用户的进程7. 显示进程内存占用8. 查看进程树9. 实时监控进程10. 查看特定进程的详细信息11. 查看特定用户的进程统计…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...