LeetCode第797题: 所有可能的路径

2024-04-18 23:06

本文主要是介绍LeetCode第797题: 所有可能的路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.问题描述

2.问题分析


1.问题描述

        给你一个有 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)

2.问题分析

        思路分析:有向无环图(Directed acyclic graph, DAG)是图论中的一个概念,它指的是一个无回路的有向图。问题是要找到0节点到n − 1节点的所有路径,对于所有路径的问题,我们可以用深度优先搜索来做(广度优先搜索也可以)。

        这题让在有向无环图中输出从顶点0到顶点n-1的所有路径,可以使用dfs,从顶点0开始搜索,搜索所有路径,因为是无环的,所以搜索的时候不会出现死循环。到顶点n-1的时候就把这条路径上所有的点都保存下来。因为是dfs搜索,往下走的时候选择节点,往回走的时候要记得撤销选择。

JAVA

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {List<List<Integer>> ans = new ArrayList<>();ArrayList<Integer> path = new ArrayList<>();path.add(0);// 把起始节点0加进来dfs(graph, 0, ans, path);return ans;
}private void dfs(int[][] graph, int index, List<List<Integer>> ans, List<Integer> path) {//  到最后一个节点的时候,说明找了一个一条有效路径if (index == graph.length - 1) {ans.add(new ArrayList<>(path));return;}// 当前节点指向哪些节点(可以看做是n叉树的子节点,然后遍历他的子节点)int[] directs = graph[index];for (int i = 0; i < directs.length; i++) {path.add(directs[i]);// 把当前节点加入到路径中dfs(graph, directs[i], ans, path);// 递归path.remove(path.size() - 1); // 撤销选择}
}

C++

public:vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {vector<vector<int>> ans;vector<int> path;path.push_back(0);// 把起始节点0加进来dfs(graph, 0, ans, path);return ans;}void dfs(vector<vector<int>> &graph, int index, vector<vector<int>> &ans, vector<int> &path) {//  到最后一个节点的时候,说明找了一个一条有效路径if (index == graph.size() - 1) {ans.emplace_back(path);return;}// 当前节点指向哪些节点(可以看做是n叉树的子节点,然后遍历他的子节点)for (int g: graph[index]) {path.emplace_back(g);// 把当前节点加入到路径中dfs(graph, g, ans, path);// 递归path.pop_back(); // 撤销选择}}

C

void dfs(int **graph, int graphSize, int *graphColSize, int *returnSize,int **returnColumnSizes, int **ans, int *path, int v, int count) {//  到最后一个节点的时候,说明找了一个一条有效路径if (v == graphSize - 1) {ans[*returnSize] = malloc(count * sizeof(int));memcpy(ans[*returnSize], path, count * sizeof(int));(*returnColumnSizes)[(*returnSize)++] = count;return;}// 当前节点指向哪些节点(可以看做是n叉树的子节点,然后遍历他的子节点)for (int i = 0; i < graphColSize[v]; ++i) {path[count++] = graph[v][i];// 把当前节点加入到路径中dfs(graph, graphSize, graphColSize, returnSize, returnColumnSizes, ans, path, graph[v][i], count);// 递归count--;// 撤销选择}
}int **allPathsSourceTarget(int **graph, int graphSize, int *graphColSize, int *returnSize, int **returnColumnSizes) {int **ans = malloc(20000 * sizeof(int *));int *path = malloc(15 * sizeof(int));int v = 0;int count = 0;*returnSize = 0;*returnColumnSizes = malloc(20000 * sizeof(int));path[count++] = v;// 把起始节点0加进来dfs(graph, graphSize, graphColSize, returnSize, returnColumnSizes, ans, path, v, count);return ans;
}

Python

def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:def dfs(index):# 到最后一个节点的时候,说明找了一个一条有效路径if index == len(graph) - 1:ans.append(path[:])return# 当前节点指向哪些节点(可以看做是n叉树的子节点,然后遍历他的子节点)for direct in graph[index]:path.append(direct)  # 把当前节点加入到路径中dfs(direct)  # 递归path.pop()  # 撤销选择ans = []path = [0]dfs(0)return ans

复杂度分析

这篇关于LeetCode第797题: 所有可能的路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/916039

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR