<div>
You are given an array routes representing bus routes where routes[i] is a bus route that the i<sup>th</sup> bus repeats forever.
- For example, if
routes[0] = [1, 5, 7], this means that the0<sup>th</sup>bus travels in the sequence1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
Example 1:
<pre>Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 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. </pre>
Example 2:
<pre>Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1 </pre>
Constraints:
1 <= routes.length <= 500.1 <= routes[i].length <= 10<sup>5</sup>- All the values of
routes[i]are unique. sum(routes[i].length) <= 10<sup>5</sup>0 <= routes[i][j] < 10<sup>6</sup>0 <= source, target < 10<sup>6</sup>
</div>
题目大意：
求公交路线中最小换站次数
解题思路：
最值题且涉及到图，容易想到BFS。但此题难点在于不能将每个站作为一个节点，这样代码复杂且TLE。优化的做法是将路线作为节点，因为同一路线换站次数是一样的。属于一组节点作为一层的BFS。
解题步骤：
N/A
注意事项：
- 将整条路线作为图的节点。这些节点都位于同一层，换乘不同路线才会换到下一层，路径+1
- source和target所在的路线可能是多个，所以要将target所在的所有路线放在set中
- 邻接表计算是用两条路线是否有交集，有交集才能换乘，才能进入下一层访问，Python用set(a) & set(b)
- 如果target和source相等，返回0 (相等test case)
- 站点不存在或者不存在任何路线，就返回-1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
if target == source: # remember
return 0
graph = collections.defaultdict(list) # both set or list are fine
queue, targets, visited, distance = collections.deque(), set(), set(), collections.defaultdict(int)
for i in range(len(routes)):
if source in set(routes[i]):
queue.append(i)
visited.add(i)
distance[i] = 1
if target in set(routes[i]):
targets.add(i)
for j in range(i + 1, len(routes)):
if set(routes[i]) & set(routes[j]):
graph[i].append(j)
graph[j].append(i)
while queue:
node = queue.popleft()
if node in targets:
return distance[node]
for neighbor in graph[node]:
if neighbor in visited:
continue
queue.append(neighbor)
visited.add(neighbor)
distance[neighbor] = distance[node] + 1
return -1 # remember
TLE版本用station作为节点
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33def numBusesToDestination2(self, routes: List[List[int]], source: int, target: int) -> int:
if target == source: # remember
return 0
graph, station_to_route = collections.defaultdict(list), collections.defaultdict(set)
for j in range(len(routes)):
r = routes[j] + [routes[j][0]]
for i in range(1, len(r)):
# graph[r[i - 1]].append(r[i])
station_to_route[r[i]].add(j)
queue = collections.deque()
visited = set()
bus_num = collections.defaultdict(int) # remember collections.defaultdict(lambda: 1)
for j in station_to_route[source]:
for i in routes[j]:
if i in visited:
continue
queue.append(i)
visited.add(i)
bus_num[i] = 1
while queue:
node = queue.popleft()
if node == target:
return bus_num[node]
for j in station_to_route[node]:
for i in routes[j]:
if i in visited:
continue
queue.append(i)
visited.add(i)
bus_num[i] = bus_num[node] + 1
return -1 # remember
算法分析：
时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度<code>O(n<sup>2</sup>)</code>, n = num of routes
有两个重叠的会议，现在插入新的会议。是否再需要一个会议室取决于该新会议的开始时间小于这两个目前会议的终止时间的最小值。
