网站建设维护,1688电脑网页版,wordpress获得链接,手机版网站模板题目
给你一个数组 routes#xff0c;表示一系列公交线路。其中每个 routes[i] 表示一条公交线路#xff0c;第 i 辆公交车将会在上面循环行驶。例如#xff0c;路线 routes[0][1,5,7] 表示第 0 辆公交车会一直按序列 1-5-7-1-5-7-1-... 这样的…题目
给你一个数组 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]]source1target6输出2解释最优策略是先乘坐第一辆公交车到达车站 7然后换乘第二辆公交车到车站 6。 示例 2 输入routes [[7,12],[4,5,15],[6],[15,19],[9,12,13]]source15target 12输出-1
提示
1 routes.length 500。1 routes[i].length 10^5。routes[i] 中的所有值互不相同。sum(routes[i].length) 10^5。0 routes[i][j] 10^6。0 source, target 10^6。
解题思路
见代码
代码
class Solution {
public:int numBusesToDestination(vectorvectorint routes, int source, int target) {//记录每个公交站台可以通过的公交编号unordered_mapint,vectorint h;for(int i0;iroutes.size();i){for(int j:routes[i]){h[j].push_back(i);}}//如果没有经过 source 或者 target的公交则可以直接返回//注0 source, target 10^6 其中包括了 source target 的情况//如果两者不相等则说明不存在路径如果相等则说明不需要乘坐任何一辆公交车了if(!h.contains(source)||!h.contains(target)){if(sourcetarget) return 0;else return -1;//此处可以写成 return source ! target ? -1 : 0;} //BFS部分 广度优先搜索部分unordered_mapint,int end;//记录终点站假设为a要几路公交vectorint v(routes.size());//用于记录是否访问过queueint q;q.push(source);while (!q.empty()){int kq.front();//取第一站点 k,作为当前站点q.pop();//遍历经过k站的公交车for(int j:h[k]){int end_aend[k];//遍历j路公交的路所经过的站点 a//如果存在则说明访问过了则不需要访问了if(v[j]0){for(int a:routes[j]){if(!end.contains(a)){end[a]end_a1;q.push(a);}}}v[j]1;//用于表示我已经访问过该路车了}}return end.contains(target)?end[target]:-1;//查看是否有target的记录如果没有则说明找不到此路返回-1}
};
