資訊專欄INFORMATION COLUMN
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.
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72397.html
摘要：遍歷路徑，找到所有可以到達終點節(jié)點的路徑就是結(jié)果。提示中說保證輸入為有向無環(huán)圖，所以我們可以認為節(jié)點間一定有著某種排列的順序，從頭到尾怎樣可以有最多的路徑呢，那就是在保證沒有環(huán)路的情況下，所有節(jié)點都盡可能多的連接著其他節(jié)點。 ...
摘要：只要我們能夠有一個以某一中間路徑和為的哈希表，就可以隨時判斷某一節(jié)點能否和之前路徑相加成為目標值。 最新更新請見：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...
摘要：題目示例題目解析此題是等腰三角形，上下之間的關(guān)系簡化為上下相鄰的三個數(shù)，相鄰，大小關(guān)系是在下方二選一上方的數(shù)值，必然正確。根據(jù)此思路，可以或者，由于可以簡化，所以動態(tài)規(guī)劃方法。代碼普通代碼，較慢動態(tài)規(guī)劃，簡練 題目： Given a triangle, find the minimum path sum from top to bottom. Each step you may mov...
摘要：初始化項目添加開發(fā)基礎(chǔ)包添加添加測試工具添加初始化配置這會在你的項目根目錄新建一個文件現(xiàn)在的目錄結(jié)構(gòu)如下文件解析這是的配置文件，默認僅啟用了幾項，我一般的配置如下添加了幾條添加文件內(nèi) 初始化 NPM 項目 mkdir project-name cd project-name npm init 添加開發(fā)基礎(chǔ)包 添加 TypeScript yarn add typescript -D 添加...
摘要：解題思路利用遞歸，對于每個根節(jié)點，只要左子樹和右子樹中有一個滿足，就返回每次訪問一個節(jié)點，就將該節(jié)點的作為新的進行下一層的判斷。代碼解題思路本題的不同點是可以不從開始，不到結(jié)束。代碼當前節(jié)點開始當前節(jié)點左節(jié)點開始當前節(jié)點右節(jié)點開始 Path SumGiven a binary tree and a sum, determine if the tree has a root-to-lea...
閱讀 759·2023-04-26 01:30
閱讀 3309·2021-11-24 10:32
閱讀 2197·2021-11-22 14:56
閱讀 1994·2021-11-18 10:07
閱讀 563·2019-08-29 17:14
閱讀 636·2019-08-26 12:21
閱讀 3115·2019-08-26 10:55
閱讀 2951·2019-08-23 18:09
