[LeetCode] 815. Bus Routes

[grandyang]

 

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 直接当作邻接链表来进行图的遍历，其实是不对的，因为 routes 数组的含义是，某个公交所能到达的站点，而不是某个站点所能到达的其他站点。这里出现了两种不同的结点，分别是站点和公交。而 routes 数组建立的是公交和其站点之间的关系，那么应该将反向关系数组也建立出来，即要知道每个站点有哪些公交可以到达。由于这里站点的标号不一定是连续的，所以可以使用 HashMap，建立每个站点和其属于的公交数组之间的映射。由于一个站点可以被多个公交使用，所以要用个数组来保存公交。既然这里求的是最少使用公交的数量，那么就类似迷宫遍历求最短路径的问题，BFS 应该是首先被考虑的解法。用队列 queue 来辅助，首先将起点S排入队列中，然后还需要一个 HashSet 来保存已经遍历过的公交（注意这里思考一下，为啥放的是公交而不是站点，因为统计的是最少需要坐的公交个数，这里一层就相当于一辆公交，最小的层数就是公交数），这些都是 BFS 的标配，应当已经很熟练了。在最开头先判断一下，若起点和终点相同，那么直接返回0，因为根本不用坐公交。否则开始 while 循环，先将结果 res 自增1，因为既然已经上了公交，那么公交个数至少为1，初始化的时候是0。这里使用 BFS 的层序遍历的写法，就是当前所有的结点都当作深度相同的一层，至于为何采用这种倒序遍历的 for 循环写法，是因为之后队列的大小可能变化，放在判断条件中可能会出错。在 for 循环中，先取出队首站点，然后要去 HashMap 中去遍历经过该站点的所有公交，若某个公交已经遍历过了，直接跳过，否则就加入 visited 中。然后去 routes 数组中取出该公交的所有站点，如果有终点，则直接返回结果 res，否则就将站点排入队列中继续遍历，参见代码如下：

 

解法一：

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if (S == T) return 0;
        int res = 0;
        unordered_map<int, vector<int>> stop2bus;
        queue<int> q{{S}};
        unordered_set<int> visited;
        for (int i = 0; i < routes.size(); ++i) {
            for (int j : routes[i]) {
                stop2bus[j].push_back(i);
            }
        }
        while (!q.empty()) {
            ++res;
            for (int i = q.size(); i > 0; --i) {
                int t = q.front(); q.pop();
                for (int bus : stop2bus[t]) {
                    if (visited.count(bus)) continue;
                    visited.insert(bus);
                    for (int stop : routes[bus]) {
                        if (stop == T) return res;
                        q.push(stop);
                    }
                }
            }
        }
        return -1;
    }
};

 

下面这种方法也是 BFS 解法，思路上跟上面的解法没有啥大的区别，就是数据结构的写法上略有不同。这里的队列 queue 放的是一个由站点和公交个数组成的 pair 对儿，这样就不用维护一个全局的最小公交数变量了。当然反向关系数组还是要建立出来的，即要知道每个站点有哪些公交可以到达。和上面稍有不同的是，使用了 HashSet 来保存经过某个站点的所有公交，但其实和用数组并没啥区别，因为这里没有查询需求，无法发挥 HashSet 的优势。由于对于每个站点，都保存了当达该站点所需的最少公交数，那么就不需要使用层序遍历的 BFS 的写法，直接用最一般的写法即可。还有一个不同之处在于，这里的 visited 保存的是遍历过的站点，而不再是公交了。在 while 循环中，首先将队首元素取出来，这里就取出来了当前站点 cur，和最少公交数 cnt，若当前站点就是终点，那就直接返回 cnt。否则遍历经过当前站点的所有公交，对每辆公交，再去遍历去所有站点，若站点已经被遍历过了，直接跳过，否则就加入 visited 中，并和 cnt+1 一起组成个 pair 对儿排入队列中继续遍历，参见代码如下：

 

解法二：

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if (S == T) return 0;
        unordered_map<int, unordered_set<int>> stop2bus;
        queue<pair<int, int>> q{{{S, 0}}};
        unordered_set<int> visited;
        for (int i = 0; i < routes.size(); ++i) {
            for (int j : routes[i]) {
                stop2bus[j].insert(i);
            }
        }
        while (!q.empty()) {
            int cur = q.front().first, cnt = q.front().second; q.pop();
            if (cur == T) return cnt;
            for (int bus : stop2bus[cur]) {
                for (int stop : routes[bus]) {
                    if (visited.count(stop)) continue;
                    visited.insert(stop);
                    q.push({stop, cnt + 1});
                }
            }
        }
        return -1;
    }
};

 

Github 同步地址：

#815

 

参考资料：

https://leetcode.com/problems/bus-routes/

https://leetcode.com/problems/bus-routes/discuss/122712/Simple-Java-Solution-using-BFS

https://leetcode.com/problems/bus-routes/discuss/122771/C%2B%2BJavaPython-BFS-Solution

 

LeetCode All in One 题目讲解汇总(持续更新中...)