[Swift]LeetCode797. 所有可能的路径 | All Paths From Source to Target

概述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. 

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.

@H_502_16@Example:input: [[1,2],[3],[]] Output: [[0,3],[0,2,3]] Explanation: The graph looks like this:0--->1| |v v2--->3There 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.

给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了a→b你就不能从b→a）空就是没有下一个结点了。

@H_502_16@示例:输入: [[1,[]] 输出: [[0,3]] 解释: 图是这样的:0--->1| |v v2--->3这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.

提示:

结点的数量会在范围 [2,15] 内。 你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

 

84ms

@H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 4 var result : [[Int]] = [] 5 addpath([0],from: graph,graph,&result) 6 7 return result 8 } 9 func addpath(_ current : [Int],from graph: [[Int]],_ oriGraph:[[Int]],_ store:inout [[Int]]) {10 11 if graph.count == 0 || graph[0].count == 0{12 store.append(current)13 return14 }15 16 for g in graph[0] {17 addpath(current + [g],from: Array(oriGraph[g..<oriGraph.count]),oriGraph,&store)18 }19 }20 }

132ms

@H_502_16@ 1 class Solution { 2 private var cache = [Int:[[Int]]]() 3 private var length = 0 4 5 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 6 var graph = graph; length = graph.count - 1 7 cache[length] = [[Int]]() 8 defer { 9 cache = [Int:[[Int]]]()10 }11 return mIDdleTarget(0,&graph)12 }13 14 private func mIDdleTarget(_ start: Int,_ graph: inout [[Int]]) -> [[Int]] {15 if (cache[start] == nil) {16 var tmpAns = [[Int]]()17 for next in graph[start] {18 if (next == length) {19 tmpAns.append([start,next])20 } else {21 for path in mIDdleTarget(next,&graph) {22 tmpAns.append([start]+path)23 }24 }25 }26 cache[start] = tmpAns27 }28 return cache[start]!29 }30 }

140ms

@H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 var solution = [[Int]]() 4 5 var working = [[0]] 6 while !working.isEmpty { 7 // Push all working paths one node deeper 8 working = helper(graph: graph,working: working) 9 10 // These have hit the end so add to solution11 let workingSolutions = working.filter { $0.last == graph.count - 1 }12 solution.append(contentsOf: workingSolutions)13 14 // These haven‘t reached the end yet15 working = working.filter { $0.last != graph.count - 1 }16 }17 18 return solution19 }20 21 /// Push all paths forward one node22 /// Prune all paths that are dead ends/ don‘t lead to last node23 func helper(graph: [[Int]],working: [[Int]]) -> [[Int]] {24 var newWorking = [[Int]]()25 26 for w in working {27 guard let currentNode = w.last,28 currentNode < graph.count else {29 continue30 }31 32 let nextNodes = graph[currentNode]33 guard !nextNodes.isEmpty else {34 continue35 }36 37 for node in nextNodes {38 var newPath = w39 newPath.append(node)40 41 newWorking.append(newPath)42 }43 }44 45 return newWorking46 }47 }

144ms

@H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 var array: [[Int]] = [] 4 var path = [0] 5 findpath(with: graph,index: 0,result: &array,path: &path) 6 return array 7 } 8 9 func findpath(with graph:[[Int]],index: Int,result: inout [[Int]],path: inout [Int]) {10 guard index != graph.count - 1 else {11 result.append(path)12 return13 }14 for i in graph[index] {15 var tempPath = path + [i]16 findpath(with: graph,index: i,result: &result,path: &tempPath)17 }18 }19 }

156ms

@H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 return nextposition(graph,visited:[0]) 4 } 5 6 func nextposition(_ graph:[[Int]],visited:[Int]) -> [[Int]] { 7 var results = [[Int]]() 8 var latestposition = visited.last! 9 if latestposition == graph.count - 1 {10 results.append(visited)11 } else {12 for position in graph[visited.last!] {13 if visited.contains(position) {14 continue15 } else {16 var visited_new = visited17 visited_new.append(position)18 results += nextposition(graph,visited: visited_new)19 }20 }21 }22 return results23 }24 }

164ms

@H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 var results = [[Int]]() 4 search(graph.count - 1,[0],0,&results) 5 return results 6 } 7 8 func search(_ target: Int, 9 _ path: [Int],10 _ currentNode: Int,11 _ graph: [[Int]],12 _ results: inout [[Int]]) {13 if currentNode == target {14 results.append(path)15 return16 }17 for nextNode in graph[currentNode] {18 search(target,19 path + [nextNode],20 nextNode,21 &results)22 }23 }24 } Runtime: 168 ms Memory Usage: 20.7 MB @H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 var graph = graph 4 return helper(&graph,0) 5 } 6 7 func helper(_ graph:inout [[Int]],_ cur:Int) -> [[Int]] 8 { 9 if cur == graph.count - 110 {11 return [[graph.count - 1]]12 }13 var res:[[Int]] = [[Int]]()14 for neigh in graph[cur]15 {16 var arr:[[Int]] = helper(&graph,neigh)17 for i in 0..<arr.count18 {19 var path:[Int] = arr[i]20 path.insert(cur,at:0);21 res.append(path);22 } 23 }24 return res25 }26 }

208ms

@H_502_16@ 1 class Solution { 2 func allPathsSourceTarget(_ graph: [[Int]]) -> [[Int]] { 3 return dfs(0,graph) 4 } 5 6 private func dfs(_ node: Int,_ graph: [[Int]]) -> [[Int]] { 7 var result = [[Int]]() 8 if node == (graph.count - 1) { 9 return [[node]]10 }11 12 for edge in graph[node] {13 let solutions = dfs(edge,graph)14 for sol in solutions {15 result.append([node] + sol)16 }17 }18 return result19 }20 } 总结

以上是内存溢出为你收集整理的[Swift]LeetCode797. 所有可能的路径 | All Paths From Source to Target全部内容，希望文章能够帮你解决[Swift]LeetCode797. 所有可能的路径 | All Paths From Source to Target所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。