[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? 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:
给一个有? 二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点(译者注:有向图是有方向的,即规定了a→b你就不能从b→a)空就是没有下一个结点了。 示例: 输入: [[1,[]] 输出: [[0,3]] 解释: 图是这样的: 0--->1 | | v v 2--->3 这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3. 提示:
? 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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |