[每日一题] 115. 公交路线(数组、bfs、哈希、多方法)

1. 题目来源

链接:公交路线
来源:LeetCode

2. 题目说明

我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如,有一条路线 routes[0] = [1, 5, 7],表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->… 的车站路线行驶。

假设我们从 S 车站开始(初始时不在公交车上),要去往 T 站。 期间仅可乘坐公交车,求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。

示例1:

输入:
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出: 2
解释:
最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。

说明:

  • 1 <= routes.length <= 500.
  • 1 <= routes[i].length <= 500.
  • 0 <= routes[i][j] < 10 ^ 6.

3. 题目解析

方法一:依据bfs,采用哈希map、set解法

这道题给了一堆公交线路表,然后给了起点和终点,问最少要换乘几辆公交可以从起点到达终点。

这题容易进的一个误区就是把 routes 直接当作邻接链表来进行图的遍历,其实是不对的。因为 routes 数组的含义是,某个公交所能到达的站点,而不是某个站点所能到达的其他站点。这里出现了两种不同的结点,分别是站点和公交。而 routes 数组建立的是公交和其站点之间的关系,那么应该将反向关系数组也建立出来,即要知道每个站点有哪些公交可以到达。由于这里站点的标号不一定是连续的,所以可以使用 HashMap,建立每个站点和其属于的公交数组之间的映射

由于一个站点可以被多个公交使用,所以要用个数组来保存公交。既然这里求的是最少使用公交的数量,那么就类似迷宫遍历求最短路径的问题,BFS 应该是首先被考虑的解法。用队列 queue 来辅助,首先将起点S排入队列中,然后还需要一个 HashSet 来保存已经遍历过的公交(注意这里思考一下,为啥放的是公交而不是站点,因为统计的是最少需要坐的公交个数,这里一层就相当于一辆公交,最小的层数就是公交数),这些都是 BFS 的标配,应当已经很熟练了。

在最开头先判断一下,若起点和终点相同,那么直接返回0,因为根本不用坐公交。否则开始 while 循环,先将结果 res 自增1,因为既然已经上了公交,那么公交个数至少为1,初始化的时候是0。这里使用 BFS 的层序遍历的写法,就是当前所有的结点都当作深度相同的一层,至于为何采用这种倒序遍历的 for 循环写法,是因为之后队列的大小可能变化,放在判断条件中可能会出错。在 for 循环中,先取出队首站点,然后要去 HashMap 中去遍历经过该站点的所有公交,若某个公交已经遍历过了,直接跳过,否则就加入 visited 中。然后去 routes 数组中取出该公交的所有站点,如果有终点,则直接返回结果 res,否则就将站点排入队列中继续遍历,参见代码如下:

// 执行用时 :116 ms, 在所有 C++ 提交中击败了96.52%的用户
// 内存消耗 :34.4 MB, 在所有 C++ 提交中击败了67.84%的用户
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,采用pair、哈希set解法

下面这种方法也是 BFS 解法,思路上跟上面的解法没有啥大的区别,就是数据结构的写法上略有不同

这里的队列 queue 放的是一个由站点和公交个数组成的 pair 对,这样就不用维护一个全局的最小公交数变量了。当然反向关系数组还是要建立出来的,即要知道每个站点有哪些公交可以到达。和上面稍有不同的是,使用了 HashSet 来保存经过某个站点的所有公交,但其实和用数组并没啥区别,因为这里没有查询需求,无法发挥 HashSet 的优势。

由于对于每个站点,都保存了到达该站点所需的最少公交数,那么就不需要使用层序遍历的 bfs的写法,直接用最一般的写法即可。还有一个不同之处在于,这里的 visited 保存的是遍历过的站点,而不再是公交了。在 while 循环中,首先将队首元素取出来,这里就取出来了当前站点 cur,和最少公交数 cnt,若当前站点就是终点,那就直接返回 cnt。否则遍历经过当前站点的所有公交,对每辆公交,再去遍历去所有站点,若站点已经被遍历过了,直接跳过,否则就加入 visited 中,并和 cnt+1 一起组成个 pair 对儿排入队列中继续遍历,参见代码如下:

// 执行用时 :2228 ms, 在所有 C++ 提交中击败了5.23%的用户
// 内存消耗 :53.3 MB, 在所有 C++ 提交中击败了17.18%的用户
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;
    }
};
[每日一题] 115. 公交路线(数组、bfs、哈希、多方法)[每日一题] 115. 公交路线(数组、bfs、哈希、多方法) Y_puyu 发布了208 篇原创文章 · 获赞 42 · 访问量 1万+ 私信 关注
上一篇:怎么找115资源那里找


下一篇:115怎么搜索资源啊