[Swift]LeetCode1129.颜色交替的最短路径|ShortestPathwithAlternatingColors ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn't exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

在一个有向图中，节点分别标记为 0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色，且存在自环或平行边。

red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地，blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的最短路径的长度，且路径上红色边和蓝色边交替出现。如果不存在这样的路径，那么 answer[x] = -1。

示例 1：

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

示例 3：

输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]

示例 4：

输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]

示例 5：

输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]

提示：

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

Runtime: 68 ms

Memory Usage: 21 MB

 1 class Solution {
 2     var n:Int = 0
 3     func shortestAlternatingPaths(_ n: Int, _ red_edges: [[Int]], _ blue_edges: [[Int]]) -> [Int] {
 4         var rGraph:[[Int]] = [[Int]]()
 5         self.n = n
 6         build(&rGraph, red_edges)
 7         var bGraph:[[Int]] = [[Int]]()
 8         build(&bGraph, blue_edges)
 9         
10         var dist:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:n),count:2)
11         for i in 0..<2
12         {
13             for j in 0..<n
14             {
15                 dist[i][j] = Int.max
16             }
17         }
18         dist[0][0] = 0
19         dist[1][0] = 0
20         var queue:[[Int]] = [[Int]]()
21         queue.append([0, 0])
22         queue.append([0, 1])
23         
24         while(!queue.isEmpty)
25         {
26             var cur:[Int] = queue.removeFirst()
27             if cur[1] == 0
28             {
29                 for u in rGraph[cur[0]]
30                 {
31                     if dist[1][u] == Int.max
32                     {
33                         dist[1][u] = dist[cur[1]][cur[0]] + 1
34                         queue.append([u, 1])
35                     }                    
36                 }
37             }
38             else
39             {
40                 for u in bGraph[cur[0]]
41                 {
42                     if dist[0][u] == Int.max
43                     {
44                         dist[0][u] = dist[cur[1]][cur[0]] + 1
45                         queue.append([u, 0])
46                     }
47                 }
48             }            
49         }
50         var ans:[Int] = [Int](repeating:0,count:n)
51         for i in 0..<n
52         {
53             ans[i] = min(dist[0][i], dist[1][i]);
54             if ans[i] == Int.max
55             {
56                 ans[i] = -1
57             }
58         }
59         return ans
60     }
61     
62     func build(_ graph:inout [[Int]],_ edges:[[Int]])
63     {
64         graph = [[Int]](repeating:[Int](),count:n)
65         for i in 0..<edges.count
66         {
67             let u:Int = edges[i][0]
68             let v:Int = edges[i][1]
69             graph[u].append(v)
70         }
71     }
72 }

76ms

 1 class Solution {
 2     func shortestAlternatingPaths(_ n: Int, _ red_edges: [[Int]], _ blue_edges: [[Int]]) -> [Int] {    
 3         var reds = [[Int]](repeating: [Int](), count: n)
 4         var blues = reds
 5         for e in red_edges {
 6             var arr = reds[e[0]]
 7             arr.append(e[1])
 8             reds[e[0]] = arr
 9         }
10         for e in blue_edges {
11             var arr = blues[e[0]]
12             arr.append(e[1])
13             blues[e[0]] = arr
14         }
15         var q = [[0, 0]]
16         var res = [Int](repeating: -1, count: n)
17         var moves = 0
18         var seens = Set<String>()
19         while !q.isEmpty {
20             let size = q.count
21             for _ in 0..<size {
22                 var cur = q.removeFirst()
23                 let key = "\(cur[0])" + " " + "\(cur[1])"
24                 if seens.contains(key) {
25                     continue
26                 }
27                 seens.insert(key)
28                 if res[cur[0]] == -1 {
29                     res[cur[0]] = moves
30                 }
31 
32                 if cur[1] == 2 || cur[1] == 0 {
33                     if reds[cur[0]].count > 0 {
34                         for child in reds[cur[0]] {
35                             q.append([child, 1])
36                         }
37                     }
38                 }
39 
40                 if cur[1] == 1 || cur[1] == 0 {
41                     if blues[cur[0]].count > 0 {
42                         for child in blues[cur[0]] {
43                             q.append([child, 2])
44                         }
45                     }
46                 }
47             }
48             moves += 1
49         }
50         return res
51     }
52 }

92ms

 1 class Solution {
 2     func shortestAlternatingPaths(_ n: Int, _ red_edges: [[Int]], _ blue_edges: [[Int]]) -> [Int] {
 3         var r_graph = [Int: [Int]]()
 4         var b_graph = [Int: [Int]]()
 5         var isVisited = Set<Int>()
 6         for edge in red_edges {
 7             r_graph[edge[0]] = r_graph[edge[0]] ?? [Int]()
 8             r_graph[edge[0]]!.append(edge[1])
 9         }
10         
11         for edge in blue_edges {
12             b_graph[edge[0]] = b_graph[edge[0]] ?? [Int]()
13             b_graph[edge[0]]!.append(edge[1])
14         }
15         
16         var result = [Int](repeating: -1, count: n)
17         var level = -1
18         var queue = [[-1, 0]]
19         while queue.count > 0 {
20             let size = queue.count 
21             level += 1
22             var tempQueue = [[Int]]()
23             for curr in queue {
24                 // guard !isVisited.contains(curr[1]) else { continue }
25                 // isVisited.insert(curr[1])
26                 if result[curr[1]]  == -1 {
27                     result[curr[1]] = level
28                 } else {
29                     result[curr[1]] = min(result[curr[1]], level)
30                 }
31                 
32                 if curr[0] == -1 { 
33                     if let red = r_graph[0] {
34                         for node in red {
35                             tempQueue.append([0, node])
36                         }
37                         r_graph.removeValue(forKey: 0)
38                     }
39                     
40                     if let blue = b_graph[0] {
41                         for node in blue {
42                             tempQueue.append([1, node])
43                         }
44                         b_graph.removeValue(forKey: 0)
45                     }
46                     
47                 }
48                 // last is red
49                 if curr[0] == 0 {
50                     let next = curr[1]
51                     if let blue = b_graph[next] {
52                         for node in blue {
53                             tempQueue.append([1, node])
54                         }
55                         b_graph.removeValue(forKey: next)
56                     }
57                 }
58                 
59                 if curr[0] == 1 {
60                     let next = curr[1]
61                     if let red = r_graph[next] {
62                         for node in red {
63                             tempQueue.append([0, node])
64                         }
65                         r_graph.removeValue(forKey: next)
66                     }
67                 }
68             }
69             queue = tempQueue
70             // print(queue)
71         }
72         return result
73     }
74 }

96ms

  1 class Solution {
  2     enum EdgeColor: CaseIterable {
  3         case red
  4         case blue
  5     }
  6 
  7     struct EdgeColorHelper {
  8         private init() {
  9         }
 10 
 11         static func toString(_ edgeColor: EdgeColor) -> String {
 12             switch edgeColor {
 13                 case .red:
 14                     return "R"
 15                 case .blue:
 16                     return "B"
 17             }
 18         }
 19     }
 20 
 21     struct MoveTo: Hashable, CustomDebugStringConvertible {
 22         let edgeColor: EdgeColor
 23         let from: Int
 24         let to: Int
 25 
 26         init(from: Int, to: Int, edgeColor: EdgeColor) {
 27             self.edgeColor = edgeColor
 28              self.from = from
 29             self.to = to
 30         }
 31 
 32         var debugDescription: String {
 33             return "\(self.from)->\(self.to):\(EdgeColorHelper.toString(self.edgeColor))"
 34         }
 35     }
 36 
 37     class Reachability: CustomDebugStringConvertible {
 38         private var reached = [Int:Int]() // { from zero to { to: length } }
 39 
 40          init(edges: EdgeList) {
 41             var length = 0
 42             var visited = Set<MoveTo>()
 43             var moves: [MoveTo] = [ MoveTo(from: 0, to: 0, edgeColor: .red), MoveTo(from: 0, to: 0, edgeColor: .blue) ]
 44             while moves.count > 0 {
 45                 var nextMoves = [MoveTo]()
 46                 for mv in moves {
 47                     if length > 0 {
 48                         if self.reached[mv.to] == nil { // length increases, so only worse values are possible
 49                             self.reached[mv.to] = length
 50                         }
 51                     }
 52                      edges.fillNextMoves(prevMove: mv, nextMoves: &nextMoves, visited: &visited)
 53                 }
 54                 moves = nextMoves
 55                 length += 1
 56             }
 57         }
 58 
 59         var debugDescription: String {
 60             return self.reached.sorted{ $0.key < $1.key }.map{ "  ->\($0.key): L=\($0.value)" }.joined(separator: "\n")
 61         }
 62 
 63         func length(to: Int, notFound: Int = -1) -> Int {
 64             guard to != 0 else {
 65                  return 0
 66             }
 67             return self.reached[to] ?? notFound
 68         }
 69     }
 70 
 71     class EdgeList: CustomDebugStringConvertible {
 72         private var colored = [EdgeColor:[Int:Set<Int>]]() // { color: { from: to } }
 73 
 74         init() {
 75         }
 76 
 77         var debugDescription: String {
 78             return self.colored.map{
 79                 "\(EdgeColorHelper.toString($0.key)): " + $0.value.sorted{ $0.key < $1.key }.map{
 80                     "\n  \($0.key) -> { " + $0.value.sorted().map{ String($0) }.joined(separator: " ") + " }"
 81                 }.joined()
 82             }.joined(separator: "\n")
 83         }
 84 
 85          func add(edges: [[Int]], edgeColor: EdgeColor) {
 86               for crd in edges {
 87                 self.add(from: crd[0], to: crd[1], edgeColor: edgeColor)
 88             }
 89         }
 90 
 91         private func add(from: Int, to: Int, edgeColor: EdgeColor) {
 92             self.colored[edgeColor, default: [:]][from, default: Set<Int>()].insert(to)
 93         }
 94 
 95         func fillNextMoves(prevMove: MoveTo, nextMoves: inout [MoveTo], visited: inout Set<MoveTo>) {
 96             let nextColor: EdgeColor
 97             switch prevMove.edgeColor {
 98                 case .red:
 99                     nextColor = .blue
100                 case .blue:
101                       nextColor = .red
102             }
103 
104             guard let edges = self.colored[nextColor] else {
105                 return
106             }
107             guard let dests = edges[prevMove.to] else {
108                 return
109             }
110 
111             for to in dests {
112                 let mv = MoveTo(from: prevMove.to, to: to, edgeColor: nextColor)
113                  if visited.contains(mv) {
114                       continue
115                 }
116 
117                 visited.insert(mv)
118                 nextMoves.append(mv)
119             }
120         }
121     }
122 
123     func shortestAlternatingPaths(_ n: Int, _ red_edges: [[Int]], _ blue_edges: [[Int]]) -> [Int] {
124         let edges = EdgeList()
125           edges.add(edges: red_edges, edgeColor: .red)
126         edges.add(edges: blue_edges, edgeColor: .blue)
127 
128         let dest = Reachability(edges: edges)
129         var paths: [Int] = Array(repeating: 0, count: n)
130         for i in 0..<paths.count {
131             paths[i] = dest.length(to: i)
132         }
133         return paths
134     }
135 }