leetcode-815

LeetCode 815. 公交路线

1 题目描述

• 题目链接：815. 公交路线

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 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

2 思路

  求最少乘车数量，最简单的就是采用BFS来解决，当BFS遍历到终点时，此时的乘车次数就是最少的。

  那么如何进行遍历呢？首先当然就是从起点出发，所以就是先把起点push到队列中，然后遍历那些经过了当前站点(一开始的是当前站点就是起点source)的公交路线，将这些路线中的站点一一push到队列中，当当前遍历的路线上出现了target站点，那么此时的乘车次数就是答案，直接返回即可。而如果没有终点站点，那么乘车次数就要+1，然后遍历经过前边那些站点的公交路线，循环反复即可。当全部遍历完成后，说明到不了终点了，返回-1.

  首先我们需要知道路过某个站点的公交车都有哪些线路(方便后边的BFS遍历)，这里可以采用unordered_map<int, vector<int>>来存储，键为站点，值即为公交路线的索引，实现方式如下：

for(int i = 0; i < n; ++i) {
    for(int j = 0; j < routes[i].size(); ++j) {
        map[routes[i][j]].emplace_back(i);
    }
}

  其次，BFS进行遍历的时候可能会遍历到之前已经遍历的公交路线，那么就会陷入死循环，因而我们需要用一个变量来记录已经遍历过的公交路线，可以采用vector<bool>和set<int>两种方式来实现，遍历时如果检测到当前路线已经遍历过，那么就跳过这条路线，遍历下一条公交路线。为什么可以直接跳过这条路线呢？因为如果前边已经遍历过这条路线，说明通过这条路线无法直接到达终点，顶多也就作为中转的路线，或者干脆不坐这条线。如果是中转线，那前边中转了一次，下次还要再中转，不就瞎费工夫吗？比如这条路线为1->3->5->7->10，上次中转了，坐的是1->3，这次坐的是7->10，那上次我干脆从1->10不就OK了嘛？

  最后，当当前的公交路线中含有终点target时，此时乘车次数即为答案，直接进行返回。

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source == target)    return 0;
        int n = routes.size();
        unordered_map<int, vector<int>> map;
        for(int i = 0; i < n; ++i)  for(int j = 0; j < routes[i].size(); ++j)
            // 创建从站点到公交路线间的映射
            map[routes[i][j]].emplace_back(i);     // 索引为i的公交路线经过了站点`routes[i][j]`
        queue<int> q;               // BFS,所以用到队列
        q.push(source);             // 把起点push到队列中
        unordered_set<int> vis;     // 记录已经遍历过的路线
        int res = 0;                // 乘车次数
        
        while(!q.empty()) {
            ++res;
            int size = q.size();
            
            // 遍历队列中的站点(当前路线)
            for(int i = size; i > 0; --i) {
                int curStop = q.front();    
                q.pop();
                
                // 遍历经过当前站点的公交路线
                for(int bus: map[curStop]) {
                    if(vis.count(bus))  continue;   // 该路线已经遍历过，跳过该路线
                    vis.insert(bus);                // 该路线正在遍历
                    
                    // 遍历下一条路线的站点
                    for(int nextStop: routes[bus]) {
                        if(nextStop == target)  return res;
                        q.push(nextStop);
                    }
                }
            }
        }
        return -1;
    }
};