Re: [閒聊] 每日LeetCode
797. All Paths From Source to Target
給你一個陣列表示的有向無環圖，找出從編號0的節點到編號n-1的節點之所有可能路徑，
題目保證圖形不會出現任何循環（包括自循環）。
https://assets.leetcode.com/uploads/2020/09/28/all_1.jpg
Exaple：
Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.
思路：
1.要找出所有可能的話一定要遍歷所有節點，我們可以使用回溯法求解，當前
串列初始化時先加入一個0（因為要求出0到n-1所以必定包含且是第一個）
2.對每個節點的邊做dfs，過程中每次都把當前訪問的點加入curr，離開這個點
的時候進行回溯，如果當前編號等於n-1表示走到了終點，把目前的curr加入
結果集。
3.返回res。
Java Code：
---------------------------------
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> curr = new ArrayList<>();
curr.add(0);
dfs(graph, res, curr, 0);
return res;
}
private void dfs(int[][] graph, List<List<Integer>> res, List<Integer>
curr, int i) {
if (i == graph.length - 1) {
res.add(new ArrayList<>(curr));
}
for (int vertex : graph[i]) {
curr.add(vertex);
dfs(graph, res, curr, vertex);
curr.remove(curr.size() - 1);
}
}
}
---------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.41.110 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1672363372.A.E0B.html
※ 編輯: Rushia (1.160.41.110 臺灣), 12/30/2022 09:26:41
推
12/30 09:27,
2年前
, 1F
12/30 09:27, 1F
討論串 (同標題文章)
完整討論串 (本文為第 168 之 719 篇)：