Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode - 所有可能的路径

LeetCode - 所有可能的路径

作者头像
晓痴
发布于 2019-07-24 06:13:18
发布于 2019-07-24 06:13:18
77900
代码可运行
举报
文章被收录于专栏:曌的晓痴曌的晓痴
运行总次数:0
代码可运行

我又重新开始更新LeetCode了,以后工作日更新LeetCode,周末更新东野圭吾的小说

这题是LeetCode第797题,中等难度。

原题地址:https://leetcode-cn.com/problems/all-paths-from-source-to-target/

题目描述

给一个有 n 个结点的有向无环图,找到所有从 0 到 n-1 的路径并输出(不要求按顺序)

二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点(译者注:有向图是有方向的,即规定了a→b你就不能从b→a)空就是没有下一个结点了。

示例:

输入: [[1,2], [3], [3], []]

输出: [[0,1,3],[0,2,3]]

解释: 图是这样的:

0--->1

| |

v v

2--->3

这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.

提示:

结点的数量会在范围 [2, 15] 内。

你可以把路径以任意顺序输出,但在路径内的结点的顺序必须保证。

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/all-paths-from-source-to-target

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

再次使用递归的思想,新建方法allPathsSourceTarget(int[][], int),第一个参数表示图,第二个参数表示当前访问到第几个节点。

从第0个节点开始,如果当前是最后一个节点,也就是n等于数组的大小,那么就返回一条路径;否则,为每条路径都添加当前节点的访问;

最后返回的List<List>就是最后的所有的0到n-1的路径。

中文官网题解:

https://leetcode-cn.com/problems/all-paths-from-source-to-target/solution/

个人题解:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        return allPathsSourceTarget(graph, 0);
    }

    /**
     * 实际处理
     *
     * @param graph 图
     * @param n     当前是第几个节点
     * @return 路径
     */
    private List<List<Integer>> allPathsSourceTarget(int[][] graph, int n) {
        List<List<Integer>> lists = new ArrayList<>();
        // 如果当前是最后一个节点,则直接返回一条路径,路径只有当前节点
        if (n == graph.length - 1) {
            List<Integer> path = new ArrayList<>();
            path.add(graph.length - 1);
            lists.add(path);
            return lists;
        }
        // 遍历该节点可以通往其他节点的路,将当前节点添加在路径最前
        for (int i : graph[n]) {
            for (List<Integer> path : allPathsSourceTarget(graph, i)) {
                path.add(0, n);
                lists.add(path);
            }
        }
        return lists;
    }

}

结果:

虽然没有进5ms,不过还是战胜了很多人呀。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-07-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 曌的晓痴 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode-797-所有可能的路径
题目来自于力扣https://leetcode-cn.com/problems/all-paths-from-source-to-target
benym
2022/07/14
4490
LeetCode 797. 所有可能的路径(DFS)
给一个有 n 个结点的有向无环图,找到所有从 0 到 n-1 的路径并输出(不要求按顺序)
Michael阿明
2020/07/13
7660
LeetCode 797. 所有可能的路径(DFS)
LeetCode:所有可能的路径_797
给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
Yuyy
2022/06/28
3670
LeetCode:所有可能的路径_797
几道入门的回溯题 | LeetCode
这周写的几道题整体上都是回溯类型的,也都是些入门级的回溯问题。整体有一套回溯的模板,周末了做个简单的总结记录,也是为了“交作业”哈。
做棵大树
2022/09/27
2870
LeetCode - 不邻接植花
这题是LeetCode第136?次周赛的题目,难度是Easy,本来可以靠这题答对挺近周赛前100名,结果我看了眼题目后,就出去吃饭了。于是就在饭桌上思考怎么解题,最后在结束前把代码写了出来,但是由于有些BUG,所以在改BUG的时候周赛就结束了....这可能是我最靠近前100的一次。
晓痴
2019/07/24
4950
LeetCode - 不邻接植花
LeetCode通关:连刷三十九道二叉树,刷疯了!
大家好,我是拿输出博客来督促自己刷题的老三,这一节我们来刷二叉树,二叉树相关题目在面试里非常高频,而且在力扣里数量很多,足足有几百道,不要慌,我们一步步来。我的文章很长,你们 收藏一下。
三分恶
2021/09/08
8530
LeetCode通关:连刷十四题,回溯算法完全攻略
例如我们在查找二叉树所有路径的时候,查找完一个路径之后,还需要回退,接着找下一个路径。
三分恶
2021/09/23
9940
LeetCode通关:连刷十四题,回溯算法完全攻略
算法笔记学习-链表
灵活使用递归。构造递归条件,使用递归可以巧妙的解题。不过需要注意有些题目不能使用递归,因为递归深度太深会导致超时和栈溢出。
买唯送忧
2021/05/29
2670
剑指offer--二叉树中和为某一值的路径
题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
AI那点小事
2020/04/20
3060
leetcode 剑指 Offer 32 - II. 从上到下打印二叉树 II
链接: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
手撕代码八百里
2020/07/28
6410
​LeetCode刷题实战261:以图判树
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/05/28
4360
​LeetCode刷题实战261:以图判树
图论算法基础(修订版)
PS:这篇文章是之前 为什么我没写过「图」相关的算法?的修订版,主要是因为旧文中缺少 visited 数组和 onPath 数组的讨论,这里补上,同时将一些表述改得更准确,文末附带图论进阶算法。
labuladong
2021/12/21
8600
图论算法基础(修订版)
☆打卡算法☆LeetCode 113、路径总和 II 算法解析
“给定一个二叉树根节点和目标整数,找出所有符合从根节点到目标节点的值等于目标值的路径。”
恬静的小魔龙
2022/08/07
2520
☆打卡算法☆LeetCode 113、路径总和 II  算法解析
LeetCode 802. 找到最终的安全状态(逆向图+拓扑排序)
在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。
Michael阿明
2021/02/19
4250
Android 启动优化(二) - 拓扑排序的原理以及解题思路
春节之前,更新了一篇博客 Android 启动优化(一) - 有向无环图,反响还不错,今天,让我们一起来看一下,怎样用代码实现有向无环图。
程序员徐公
2021/03/15
6520
数据结构高频面试题-图
图的基础概念图的基础算法1. 图的遍历深度优先搜索遍历(DFS)广度优先搜索遍历(BFS)2. 单源最短路径问题(Dijkstra算法)3. 拓扑排序4. 最小生成树Kruskal算法(加边法)Prim算法(加点法)经典面试题1.克隆图2.课程表II3.网络延迟问题4.除法求值5.最小高度树6.重新安排行程7. 冗余连接
小萌哥
2020/07/20
2.4K0
LeetCode 1059. 从始点到终点的所有路径(回溯)
给定有向图的边 edges,以及该图的始点 source 和目标终点 destination,确定从始点 source 出发的所有路径是否最终结束于目标终点 destination,即:
Michael阿明
2021/02/19
1.2K0
​LeetCode刷题实战40:组合总和 II
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
程序员小猿
2021/01/20
3550
​LeetCode刷题实战40:组合总和 II
二叉树中和为某一值的路径
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
MickyInvQ
2021/12/07
4240
二叉树中和为某一值的路径
判断二分图
如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。
你的益达
2020/08/05
3120
相关推荐
LeetCode-797-所有可能的路径
更多 >
领券
💥开发者 MCP广场重磅上线!
精选全网热门MCP server,让你的AI更好用 🚀
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验