JAVA程序设计：公交路线（LeetCode：815）
我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0) 公交车会一直按照 1->5->7->1->5->7->1->... 的车站路线行驶。
假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。 期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -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.
方法一：离散化+最短路（超时版本）
我们将每个车站看做一个点，并且两点之间存在若干不同的路径，因为车站的编号有10^6这么大，但是真正不同的车站数量有限并且很小，因此我们可以考虑对车站编号进行离散化，之后我们定义一个二维数组dis[i][j]表示走到第i个车站，并且是通过第j个公交过来的最小转车次数，然后我们跑一边最短路。
class Solution {class node{int id,num,val;public node(int id,int num,int val) {this.id=id;this.num=num;this.val=val;}}public int numBusesToDestination(int[][] routes, int S, int T) {if(S==T) return 0;List list=new ArrayList<>();Queue q=new LinkedList<>();Map> map=new TreeMap<>();for(int i=0;i());map.get(p(list,routes[i][j])).add(new node(routes[i][(j+1)%routes[i].length],i,i));}for(int i=0;idis[p(list,now.id)][now.num]+val) {q.add(new node(index,numid,val));dis[p(list,index)][numid]=dis[p(list,now.id)][now.num]+val;}}}int ans=100000;for(int i=0;i list, int x) {int l=0,r=list.size()-1;while(l<=r) {int mid=(l+r)/2;if(list.get(mid)==x)return mid;if(list.get(mid) 方法二：优化后的广度优先搜索（通过）
我们将每一条公交路线（而不是每一个车站）看成图中的一个点，如果两条公交路线有交集，那么它们在图中对应的点之间就有一条边。此外，起点站 S 和终点站 T 也分别是图中的一个点，如果一条公交路线包含了 S 或 T，那么也需要和 S 或 T 对应的点连一条边。此时，在这个图上从 S 到 T 的最短路径长度即为答案，我们可以用广度优先搜索来找出最短路径。
在计算两条公交路线是否有交集时，可以用的方法有很多种。例如将公交路线放在集合中，检查两个集合的交集是否为空；或者将公交路线中的车站进行递增排序，并使用双指针的方法检查是否有相同的车站。
import java.awt.Point;class Solution { public int numBusesToDestination(int[][] routes, int S, int T) {if(S==T) return 0;int n=routes.length;List> graph=new ArrayList<>();for(int i=0;i());}Set st=new HashSet();Set targets=new HashSet();Queue q=new LinkedList();for(int i=0;i=0) {st.add(i);q.add(new Point(i,1));}if(Arrays.binarySearch(routes[i], T)>=0)targets.add(i);}while(!q.isEmpty()) {Point now=q.poll();int node=now.x,depth=now.y;if(targets.contains(node))return depth;for(Integer next : graph.get(node)) {if(!st.contains(next)) {st.add(next);q.add(new Point(next,depth+1));}}}return -1;}private boolean jud(int[] a,int[] b) {int i=0,j=0;while(i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！