加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

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

发布时间:2020-12-14 05:01:42 所属栏目:百科 来源:网络整理
导读: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

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],[]] 
Output: [[0,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.

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

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

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

提示:

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

?

84ms

 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             return
14         }
15         
16         for g in graph[0] {
17             addPath(current + [g],from: Array(oriGraph[g..<oriGraph.count]),oriGraph,&store)
18         }
19     }
20 }

132ms

 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] = tmpAns
27         }
28         return cache[start]!
29     }
30 }

140ms

 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 solution
11             let workingSolutions = working.filter { $0.last == graph.count - 1 }
12             solution.append(contentsOf: workingSolutions)
13             
14             // These haven‘t reached the end yet
15             working = working.filter { $0.last != graph.count - 1 }
16         }
17         
18         return solution
19     }
20     
21     /// Push all paths forward one node
22     /// Prune all paths that are dead ends/ don‘t lead to last node
23     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                 continue
30             }
31             
32             let nextNodes = graph[currentNode]
33             guard !nextNodes.isEmpty else {
34                 continue
35             }
36             
37             for node in nextNodes {
38                 var newPath = w
39                 newPath.append(node)
40                 
41                 newWorking.append(newPath)
42             }
43         }
44         
45         return newWorking
46     }
47 }

144ms

 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         return
13     }
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

 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                     continue
15                 } else {
16                     var visited_new = visited
17                     visited_new.append(position)
18                     results += nextPosition(graph,visited: visited_new)
19                 }
20             }
21         }
22         return results
23     }
24 }

164ms

 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             return
16         }
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
 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 - 1
10         {
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.count
18             {
19                 var path:[Int] = arr[i]
20                 path.insert(cur,at:0);
21                 res.append(path);
22             }                
23         }
24         return res
25     }
26 }

208ms

 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 result
19     }
20 }

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读