Hard
题目描述
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
- 例如，路线
routes[0] = [1, 5, 7]表示第一辆公交车会一直按序列1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...这样的路线行驶。
现在从 source 车站出发（你一开始不在任何公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 ，然后换乘第二辆公交车到车站 6 。
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
提示：
1 <= routes.length <= 5001 <= routes[i].length <= 10^5routes[i]中的所有值 互不相同sum(routes[i].length) <= 10^50 <= routes[i][j] < 10^60 <= source, target < 10^6
解题思路
这道题是一个典型的图论 BFS 问题，关键在于如何建图和如何进行搜索。
核心思路：
换车模型：我们需要将问题转化为"在公交线路之间换乘"的问题，而不是在车站之间移动的问题。
建图策略：
- 首先建立车站到公交线路的映射，即每个车站可以乘坐哪些公交线路
- 然后构建公交线路之间的连通关系，如果两条线路有共同的车站，则它们之间可以换乘
BFS搜索：
- 从包含起点的所有公交线路开始 BFS
- 每次扩展时，找到当前线路能到达的所有车站，然后找到这些车站连接的其他线路
- 当找到包含终点的线路时，返回当前步数
算法步骤：
- 特判：如果起点等于终点，直接返回 0
- 建立车站到线路的映射关系
- 找到包含起点的所有线路作为 BFS 的起始点
- 使用 BFS 搜索，每次扩展一个线路，找到该线路连接的其他线路
- 当找到包含终点的线路时返回结果
时间复杂度主要取决于线路数量和车站数量，空间复杂度用于存储映射关系和访问状态。
代码实现
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if (source == target) return 0;
// 建立车站到线路的映射
unordered_map<int, vector<int>> stopToRoutes;
for (int i = 0; i < routes.size(); i++) {
for (int stop : routes[i]) {
stopToRoutes[stop].push_back(i);
}
}
// 如果起点或终点不存在任何线路，返回-1
if (stopToRoutes.find(source) == stopToRoutes.end() ||
stopToRoutes.find(target) == stopToRoutes.end()) {
return -1;
}
// BFS
queue<int> q;
unordered_set<int> visitedRoutes;
// 将包含起点的所有线路加入队列
for (int route : stopToRoutes[source]) {
q.push(route);
visitedRoutes.insert(route);
}
int buses = 1;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int currentRoute = q.front();
q.pop();
// 检查当前线路是否包含终点
for (int stop : routes[currentRoute]) {
if (stop == target) {
return buses;
}
}
// 扩展到相邻的线路
for (int stop : routes[currentRoute]) {
for (int nextRoute : stopToRoutes[stop]) {
if (visitedRoutes.find(nextRoute) == visitedRoutes.end()) {
visitedRoutes.insert(nextRoute);
q.push(nextRoute);
}
}
}
}
buses++;
}
return -1;
}
};
class Solution:
def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
if source == target:
return 0
# 建立车站到线路的映射
stop_to_routes = defaultdict(list)
for i, route in enumerate(routes):
for stop in route:
stop_to_routes[stop].append(i)
# 如果起点或终点不存在任何线路，返回-1
if source not in stop_to_routes or target not in stop_to_routes:
return -1
# BFS
queue = deque()
visited_routes = set()
# 将包含起点的所有线路加入队列
for route in stop_to_routes[source]:
queue.append(route)
visited_routes.add(route)
buses = 1
while queue:
for _ in range(len(queue)):
current_route = queue.popleft()
# 检查当前线路是否包含终点
if target in routes[current_route]:
return buses
# 扩展到相邻的线路
for stop in routes[current_route]:
for next_route in stop_to_routes[stop]:
if next_route not in visited_routes:
visited_routes.add(next_route)
queue.append(next_route)
buses += 1
return -1
public class Solution {
public int NumBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
// 建立车站到线路的映射
var stopToRoutes = new Dictionary<int, List<int>>();
for (int i = 0; i < routes.Length; i++) {
foreach (int stop in routes[i]) {
if (!stopToRoutes.ContainsKey(stop)) {
stopToRoutes[stop] = new List<int>();
}
stopToRoutes[stop].Add(i);
}
}
// 如果起点或终点不存在任何线路，返回-1
if (!stopToRoutes.ContainsKey(source) || !stopToRoutes.ContainsKey(target)) {
return -1;
}
// BFS
var queue = new Queue<int>();
var visitedRoutes = new HashSet<int>();
// 将包含起点的所有线路加入队列
foreach (int route in stopToRoutes[source]) {
queue.Enqueue(route);
visitedRoutes.Add(route);
}
int buses = 1;
while (queue.Count > 0) {
int size = queue.Count;
for (int i = 0; i < size; i++) {
int currentRoute = queue.Dequeue();
// 检查当前线路是否包含终点
if (routes[currentRoute].Contains(target)) {
return buses;
}
// 扩展到相邻的线路
foreach (int stop in routes[currentRoute]) {
if (stopToRoutes.ContainsKey(stop)) {
foreach (int nextRoute in stopToRoutes[stop]) {
if (!visitedRoutes.Contains(nextRoute)) {
visitedRoutes.Add(nextRoute);
queue.Enqueue(nextRoute);
}
}
}
}
}
buses++;
}
return -1;
}
}
var numBusesToDestination = function(routes, source, target) {
if (source === target) return 0;
// Map each stop to the buses that visit it
const stopToBuses = new Map();
for (let i = 0; i < routes.length; i++) {
for (const stop of routes[i]) {
if (!stopToBuses.has(stop)) {
stopToBuses.set(stop, []);
}
stopToBuses.get(stop).push(i);
}
}
if (!stopToBuses.has(source) || !stopToBuses.has(target)) {
return -1;
}
const queue = [source];
const visitedStops = new Set([source]);
const visitedBuses = new Set();
let buses = 0;
while (queue.length > 0) {
buses++;
const size = queue.length;
for (let i = 0; i < size; i++) {
const stop = queue.shift();
// Check all buses that visit this stop
for (const busId of stopToBuses.get(stop)) {
if (visitedBuses.has(busId)) continue;
visitedBuses.add(busId);
// Add all stops of this bus to queue
for (const nextStop of routes[busId]) {
if (nextStop === target) return buses;
if (!visitedStops.has(nextStop)) {
visitedStops.add(nextStop);
queue.push(nextStop);
}
}
}
}
}
return -1;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(N + M) | 其中 N 是所有车站的总数，M 是所有线路的总数。需要遍历所有车站建立映射，BFS 最坏情况下访问所有线路 |
| 空间复杂度 | O(N + M) | 存储车站到线路的映射关系、访问状态和 BFS 队列所需的空间 |