[Swift]LeetCode815.公交路线|BusRoutes

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

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

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

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

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

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

We have a list of bus routes. Each routes[i]is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->... 的车站路线行驶。

假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。

示例:
输入: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出: 2
解释: 
最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。

说明:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

584ms

 1 class Solution {    
 2     // BFS is easier, also faster
 3     func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
 4         if S == T { return 0 }
 5         var stopToRoutes = [Int: [Int]]()
 6         for (index, route) in routes.enumerated() {
 7             for stop in route {
 8                 if var buses = stopToRoutes[stop] {
 9                     buses.append(index)
10                     stopToRoutes[stop] = buses
11                 } else {
12                     stopToRoutes[stop] = [index]
13                 }
14             }
15         }
16         
17         //print(stopToRoutes)
18         
19         var queue = [Int]()
20         queue.append(S)
21         var visited = Set<Int>()
22         var ans = 0
23         while (!queue.isEmpty) {
24             //print(queue, visited, ans)
25             ans += 1
26             var size = queue.count
27             while (size > 0) {
28                 let last = queue.remove(at: 0)
29                 for route in (stopToRoutes[last] ?? []) {
30                     if visited.contains(route) {
31                         continue
32                     } else {
33                         visited.insert(route)
34                     }
35                     for stop in routes[route] {
36                         if stop == T {
37                             return ans
38                         }
39                         queue.append(stop)
40                     }
41                 }
42                 size -= 1
43             }  
44         }
45         return -1
46     }
47 
48     // LTE
49     // graph search: DFS
50     func numBusesToDestination1(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
51         if S == T { return 0 }
52         var stopToRoutes = [Int: [Int]]()
53         for (index, route) in routes.enumerated() {
54             for stop in route {
55                 if var buses = stopToRoutes[stop] {
56                     buses.append(index)
57                     stopToRoutes[stop] = buses
58                 } else {
59                     stopToRoutes[stop] = [index]
60                 }
61             }
62         }
63         print(stopToRoutes)
64         
65         var startI = stopToRoutes[S] ?? []
66         var targetI = stopToRoutes[T] ?? []
67         var ret = Int.max
68         var routes = routes
69         for si in startI {
70             var visited = Set<Int>()
71             find(&routes, &stopToRoutes, si, targetI, &visited, 1, &ret)
72         }
73         return ret > routes.count ? -1: ret
74     }
75     
76     private func find(_ routes: inout [[Int]], _ map: inout [Int: [Int]], _ curi: Int, _ ei: [Int], _ visited: inout Set<Int>, _ curStops: Int, _ ret: inout Int) {
77         if ei.contains(curi) {
78             ret = min(ret, curStops)
79             return
80         }
81         if visited.contains(curi) {
82             return
83         }
84         visited.insert(curi)
85         
86         let stops = routes[curi]
87         for stop in stops {
88             let buses = map[stop] ?? []
89             for route in buses {
90                 //print("find",curi, ei, stop, route, curStops)
91         
92                 find(&routes, &map, route, ei, &visited, curStops + 1, &ret)
93             }
94         }
95         
96         visited.remove(curi)
97     }
98 }

Runtime: 604 ms

Memory Usage: 24.5 MB

 1 class Solution {
 2     func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
 3         if S == T {return 0}
 4         var res:Int = 0
 5         var stop2bus:[Int:[Int]] = [Int:[Int]]()
 6         var q:[Int] = [S]
 7         var visited:Set<Int> = Set<Int>()
 8         for i in 0..<routes.count
 9         {
10             for j in routes[i]
11             {
12                 stop2bus[j,default:[Int]()].append(i)
13             }
14         }
15         while(!q.isEmpty)
16         {
17             res += 1
18             for i in stride(from:q.count,to:0,by:-1)
19             {
20                 var t:Int = q.removeFirst()
21                 for bus in stop2bus[t,default:[Int]()]
22                 {
23                     if visited.contains(bus) {continue}
24                     visited.insert(bus)
25                     for stop in routes[bus]
26                     {
27                         if stop == T {return res}
28                         q.append(stop)
29                     }
30                 }                
31             }            
32         }
33         return -1
34     }
35 }

644ms

 1 class Solution {
 2     func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
 3         var visited: Set<Int> = []
 4         var queue: [Int] = []
 5         var map: [Int: [Int]] = [:]
 6         var steps = 0
 7         
 8         if S == T {
 9             return 0
10         }
11         
12         for i in 0 ..< routes.count {
13             for j in 0 ..< routes[i].count {
14                 if map[routes[i][j]] == nil {
15                     map[routes[i][j]] = []
16                 }
17                 
18                 map[routes[i][j]]!.append(i)
19             }
20         }
21         
22         queue.append(S)
23         
24         while !queue.isEmpty {
25             var size = queue.count
26             steps += 1
27             while size > 0 {
28                 let curr = queue.removeFirst()
29                 let buses = map[curr]!
30                 for bus in buses {
31                     if !visited.contains(bus) {
32                         visited.insert(bus)
33                         for j in 0 ..< routes[bus].count {
34                             if routes[bus][j] == T {
35                                 return steps
36                             }
37                             queue.append(routes[bus][j])
38                         }
39                     }
40                 }
41                 size -= 1
42             }
43         }
44         
45         return -1
46     }
47 }

1360ms

 1 class Solution {
 2     func numBusesToDestination(_ routes: [[Int]], _ S: Int, _ T: Int) -> Int {
 3         var stops: [Int: [Int]] = [:]
 4         for (bus, route) in routes.enumerated() {
 5             for stop in route {
 6                 stops[stop, default: []].append(bus)
 7             }
 8         }
 9         var res = 0
10         var queue: [Int] = []
11         queue.append(S)
12         var visitedStops: Set<Int> = []
13         var visitedBuses: Set<Int> = []
14         while queue.isEmpty == false {
15             var n = queue.count
16             while n > 0 {
17                 n -= 1
18                 let cur = queue.removeFirst()
19                 if cur == T {
20                     return res
21                 }
22                 if visitedStops.contains(cur) {
23                     continue
24                 }
25                 visitedStops.insert(cur)
26                 for bus in (stops[cur] ?? []) {
27                     if visitedBuses.contains(bus) == true {
28                         continue
29                     }
30                     visitedBuses.insert(bus)
31                     for stop in routes[bus] {
32                         queue.append(stop)
33                     }
34                 }
35             }
36             res += 1
37         }
38         return -1
39     }
40 }