[LeetCode] 797. All Paths From Source to Target

xiaochao 发布于2019-08-16 13:49 / 772人阅读

Problem

Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:

Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

The number of nodes in the graph will be in the range [2, 15].
You can print different paths in any order, but you should keep the order of nodes inside one path.

Solution - DFS

class Solution {
    public List> allPathsSourceTarget(int[][] graph) {
        List> res = new ArrayList<>();
        List temp = new ArrayList<>();
        int firstNode = 0;
        temp.add(firstNode);
        dfs(graph, firstNode, temp, res);
        return res;
    }
    
    private void dfs(int[][] graph, int node, List temp, List> res) {
        if (node == graph.length-1) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int neighbor: graph[node]) {
            temp.add(neighbor);
            dfs(graph, neighbor, temp, res);
            temp.remove(temp.size()-1);
        }
    }
}

Solution - BFS

class Solution {
    public List> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        List> res = new ArrayList<>();
        Deque> queue = new ArrayDeque<>();
        queue.offer(Arrays.asList(0));
        
        while (!queue.isEmpty()) {
            List cur = queue.poll();
            int size = cur.size();
            if (cur.get(size-1) == n-1) {
                res.add(cur);
                continue;
            }
            
            for (int node: graph[cur.get(size-1)]) {
                List next = new ArrayList<>(cur);
                next.add(node);
                queue.offer(next);
            }
        }
        
        return res;
    }
}

云服务器服务器托管 Paths LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72397.html

【算法】剑指 Offer II 110. 所有路径｜797. 所有可能的路径（多语言实现）

摘要：遍历路径，找到所有可以到达终点节点的路径就是结果。提示中说保证输入为有向无环图，所以我们可以认为节点间一定有着某种排列的顺序，从头到尾怎样可以有最多的路径呢，那就是在保证没有环路的情况下，所有节点都尽可能多的连接着其他节点。 ...

wangdai 2021-11-23 09:51 评论0 收藏0
[Leetcode] Path Sum I & II & III 路径和1,2,3

摘要：只要我们能够有一个以某一中间路径和为的哈希表，就可以随时判断某一节点能否和之前路径相加成为目标值。最新更新请见：https://yanjia.me/zh/2019/01/... Path Sum I Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that addin...

caiyongji 2019-08-14 12:25 评论0 收藏0
leetcode-120-Triangle-等腰三角形

摘要：题目示例题目解析此题是等腰三角形，上下之间的关系简化为上下相邻的三个数，相邻，大小关系是在下方二选一上方的数值，必然正确。根据此思路，可以或者，由于可以简化，所以动态规划方法。代码普通代码，较慢动态规划，简练题目： Given a triangle, find the minimum path sum from top to bottom. Each step you may mov...

MarvinZhang 2019-07-30 16:07 评论0 收藏0
基于 TypeScript 开发 NPM 模块

摘要：初始化项目添加开发基础包添加添加测试工具添加初始化配置这会在你的项目根目录新建一个文件现在的目录结构如下文件解析这是的配置文件，默认仅启用了几项，我一般的配置如下添加了几条添加文件内初始化 NPM 项目 mkdir project-name cd project-name npm init 添加开发基础包添加 TypeScript yarn add typescript -D 添加...

songjz 2019-08-23 17:51 评论0 收藏0
[Leetcode-Tree] Path Sum I II III

摘要：解题思路利用递归，对于每个根节点，只要左子树和右子树中有一个满足，就返回每次访问一个节点，就将该节点的作为新的进行下一层的判断。代码解题思路本题的不同点是可以不从开始，不到结束。代码当前节点开始当前节点左节点开始当前节点右节点开始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...

notebin 2019-08-16 10:26 评论0 收藏0