[LeetCode] 797. All Paths From Source to Target

xiaochao 發布于2019-08-16 13:49 / 862人閱讀

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;
    }
}

云服務器 GPU云服務器 Paths LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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