資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告