LeetCode 815 Bus Routes

LeetCode

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 the 0<sup>th</sup> bus travels in the sequence 1 -> 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:

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.

Example 2:

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

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>

题目大意：

求公交路线中最小换站次数

解题思路：

最值题且涉及到图，容易想到BFS。但此题难点在于不能将每个站作为一个节点，这样代码复杂且TLE。优化的做法是将路线作为节点，因为同一路线换站次数是一样的。属于一组节点作为一层的BFS。

解题步骤：

N/A

注意事项：

1. 将整条路线作为图的节点。这些节点都位于同一层，换乘不同路线才会换到下一层，路径+1
2. source和target所在的路线可能是多个，所以要将target所在的所有路线放在set中
3. 邻接表计算是用两条路线是否有交集，有交集才能换乘，才能进入下一层访问，Python用set(a) & set(b)
4. 如果target和source相等，返回0 (相等test case)
5. 站点不存在或者不存在任何路线，就返回-1

Python代码：

def 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代码：

def 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

算法分析：

时间复杂度为O(n2)，空间复杂度O(n2), n = num of routes