每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)

这篇具有很好参考价值的文章主要介绍了每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

今日份题目:

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

graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。

示例1

每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历),图论,深度优先,leetcode,图论,算法,职场和发展,c++,数据结构

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

示例2

每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历),图论,深度优先,leetcode,图论,算法,职场和发展,c++,数据结构

输入: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. 所有可能的路径(图论&中等&深度优先遍历),图论,深度优先,leetcode,图论,算法,职场和发展,c++,数据结构

 欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!文章来源地址https://www.toymoban.com/news/detail-650743.html

到了这里,关于每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 每天一道leetcode:934. 最短的桥(图论&中等&广度优先遍历)

    给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地, 0 表示水域。 岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。 grid 中 恰好存在两座岛 。 你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。 返回必须翻转的 0 的最小数

    2024年02月12日
    浏览(53)
  • 每天一道leetcode:1466. 重新规划路线(图论&中等&广度优先遍历)

    n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。 路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条

    2024年02月12日
    浏览(48)
  • 每天一道leetcode:1306. 跳跃游戏 III(图论&中等&广度优先遍历)

    这里有一个非负整数数组 `arr`,你最开始位于该数组的起始下标 `start` 处。当你位于下标 `i` 处时,你可以跳到 `i + arr[i]` 或者 `i - arr[i]`。 请你判断自己是否能够跳到对应元素值为 0 的 **任一** 下标处。 注意,不管是什么情况下,你都无法跳到数组之外。 ``` 输入:arr = [4,

    2024年02月12日
    浏览(34)
  • 代码随想录图论 第一天 | 797.所有可能的路径 200. 岛屿数量

    代码随想录图论 第一天 | 797.所有可能的路径 200. 岛屿数量 一、797.所有可能的路径 题目链接:https://leetcode.cn/problems/all-paths-from-source-to-target/ 思路:求从0到n-1的所有路径,终止条件是当前节点为n-1。本题图的结构是group[][],group[x]表示x节点所能到达的所有节点的集合,深度

    2024年02月08日
    浏览(54)
  • 每天一道leetcode:1129. 颜色交替的最短路径(图论&中等&广度优先遍历)

    给定一个整数 n ,即有向图中的节点数,其中节点标记为 0 到 n - 1 。图中的每条边为红色或者蓝色,并且可能存在自环或平行边。 给定两个数组 redEdges 和 blueEdges ,其中: redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边, blueEdges[j] = [uj, vj] 表示图中存

    2024年02月13日
    浏览(37)
  • 每天一道leetcode:1926. 迷宫中离入口最近的出口(图论&中等&广度优先遍历)

    给你一个 m x n 的迷宫矩阵 maze ( 下标从 0 开始 ),矩阵中有空格子(用 \\\'.\\\' 表示)和墙(用 \\\'+\\\' 表示)。同时给你迷宫的入口 entrance ,用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。 每一步操作,你可以往 上 , 下 , 左 或者 右 移动一个格子。你不能进

    2024年02月12日
    浏览(34)
  • 图论算法|深度优先搜索理论基础|797.所有可能的路径|广度优先搜索BFS理论基础|200. 岛屿数量

    dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,在换方向(换方向的过程就涉及到了回溯)。 递归和回溯是相辅相成的 https://leetcode.cn/problems/all-paths-from-source-to-target/ 有向无环图(DAG): 有环无向图是指在图中存在至少一个环(Cycle)的无向图。环是

    2024年02月15日
    浏览(58)
  • 每天一道leetcode:516. 最长回文子序列(动态规划&中等)

    给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 1 = s.length = 1000 s 仅由小写英文字母组成 动态规划 ,使用二维dp数组记录[i,j]间的最大回文子序列长度

    2024年02月13日
    浏览(46)
  • 每天一道leetcode:646. 最长数对链(动态规划&中等)

    给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] = [lefti, righti] 且 lefti righti 。 现在,我们定义一种 跟随 关系,当且仅当 b c 时,数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。 找出并返回能够形成的 最长数对链的长度 。 你不需要用到所

    2024年02月12日
    浏览(45)
  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包