文档章节

[Swift]LeetCode815. 公交路线 | Bus Routes

o
 osc_y8yehimr
发布于 2019/03/20 12:26
字数 1242
阅读 5
收藏 0

精选30+云产品,助力企业轻松上云!>>>

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

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 }

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

【软件工具篇02】使用Anki克服遗忘曲线

使用Anki克服遗忘曲线 艾宾浩斯遗忘曲线 百度百科:遗忘曲线由德国心理学家艾宾浩斯研究发现,描述了人类大脑对新事物遗忘的规律。人体大脑对新事物遗忘的循序渐进的直观描述,人们可以从遗...

osc_wobxrheh
19分钟前
0
0
面向对象的理解

面向对象的三大特性 封装 继承 多态 面向对象的七大原则 单一职责原则:每一个类应该专注于做一件事情。即高内聚,低耦合。类的功能要单一,体积不要过于庞大。 开闭原则:一个对象对扩展开发...

osc_2wq8ft8d
20分钟前
11
0
Laravel Redis分布式锁实现源码分析

首先是锁的抽象类,定义了继承的类必须实现加锁、释放锁、返回锁拥有者的方法。 namespace Illuminate\Cache;abstract class Lock implements LockContract{ use InteractsWithTime;...

osc_2jegjdnw
22分钟前
0
0
【HDFS篇03】HDFS客户端操作 --- 开发环境准备

存储越困难,提取越容易 HDFS客户端操作---开发环境准备 步骤一:编译对应HadoopJar包,配置Hadoop变量 步骤二:创建Maven工程,导入pom依赖 <dependencies><dependency><groupId>ju...

osc_ds5ni1ur
23分钟前
7
0
老板,来瓶辣椒酱

最近网剧《隐秘的角落》非常的火爆,结局反转让人难以预料,但前两天发生了一场堪比史诗级大片的纠纷,纠纷的结局反转让人大跌眼镜,估计是神编剧都写不出来那样的剧本...而引发这场纠纷最核...

osc_1loi8uc4
25分钟前
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部