数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中的公交路线
假设我们有一系列公交路线。在每条routes[i]中，都有一条第i辆公交车无限循环行驶的路线。所以，如果routes[0] = [1, 5, 7]，这意味着第一辆公交车（索引为0）将按照1, 5, 7, 1, 5, 7, 1,...的顺序无限循环行驶。
现在假设我们从公交站S出发，最初不在任何公交车上，想要到达公交站T。我们需要找到到达目的地的最少乘车次数？如果无法到达，则返回-1。
例如，如果输入为[[1,2,8],[3,6,8]]，S = 1，T = 6，则输出为2。先乘坐第一辆公交车到公交站8，然后乘坐第二辆公交车到公交站6。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个映射m
- 对于i := 0，当i < r的大小，更新（i加1），执行：
- 对于j := 0，当j < r[i]的大小，更新（j加1），执行：
- 将i插入到m[r[i, j]]的末尾
- 对于j := 0，当j < r[i]的大小，更新（j加1），执行：
- 定义一个队列q，将S插入到q中
- 如果S等于T，则：
- 返回0
- 定义一个名为visited的集合
- 对于lvl := 1，当q不为空，更新（lvl加1），执行：
- sz := q的大小
- 当sz不为零时，执行：
- node := q的第一个元素，从q中删除该元素
- 对于i := 0，当i < m[node]的大小，更新（i加1），执行：
- route := m[node, i]
- 如果visited包含route，则：
- 忽略以下部分，跳到下一个迭代
- 将route插入到visited中
- 对于j := 0，当j < r[route]的大小，更新（j加1），执行：
- stop := r[route, j]
- 如果stop等于T，则：
- 返回lvl
- 将stop插入到q中
- sz减1
- 返回-1
让我们来看下面的实现来更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& r, int S, int T) {
unordered_map <int, vector <int> > m;
for(int i = 0; i < r.size(); i++){
for(int j = 0; j < r[i].size(); j++){
m[r[i][j]].push_back(i);
}
}
queue <int> q;
q.push(S);
if(S == T) return 0;
unordered_set <int> visited;
for(int lvl = 1; !q.empty(); lvl++){
int sz = q.size();
while(sz--){
int node = q.front();
q.pop();
for(int i = 0; i < m[node].size(); i++){
int route = m[node][i];
if(visited.count(route)) continue;
visited.insert(route);
for(int j = 0; j < r[route].size(); j++){
int stop = r[route][j];
if(stop == T) return lvl;
q.push(stop);
}
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,2,8}, {3,6,8}};
cout << (ob.numBusesToDestination(v, 1, 6));
}输入
{{1,2,8}, {3,6,8}}
1
6输出
2
更新于：2020年6月2日
1K+ 次浏览
广告