You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
60 lines
1.4 KiB
60 lines
1.4 KiB
package class36;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.HashMap;
|
|
|
|
// 来自三七互娱
|
|
// Leetcode原题 : https://leetcode.com/problems/bus-routes/
|
|
public class Code11_BusRoutes {
|
|
|
|
// 0 : [1,3,7,0]
|
|
// 1 : [7,9,6,2]
|
|
// ....
|
|
// 返回:返回换乘几次+1 -> 返回一共坐了多少条线的公交。
|
|
public static int numBusesToDestination(int[][] routes, int source, int target) {
|
|
if (source == target) {
|
|
return 0;
|
|
}
|
|
int n = routes.length;
|
|
// key : 车站
|
|
// value : list -> 该车站拥有哪些线路!
|
|
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
|
|
for (int i = 0; i < n; i++) {
|
|
for (int j = 0; j < routes[i].length; j++) {
|
|
if (!map.containsKey(routes[i][j])) {
|
|
map.put(routes[i][j], new ArrayList<>());
|
|
}
|
|
map.get(routes[i][j]).add(i);
|
|
}
|
|
}
|
|
ArrayList<Integer> queue = new ArrayList<>();
|
|
boolean[] set = new boolean[n];
|
|
for (int route : map.get(source)) {
|
|
queue.add(route);
|
|
set[route] = true;
|
|
}
|
|
int len = 1;
|
|
while (!queue.isEmpty()) {
|
|
ArrayList<Integer> nextLevel = new ArrayList<>();
|
|
for (int route : queue) {
|
|
int[] bus = routes[route];
|
|
for (int station : bus) {
|
|
if (station == target) {
|
|
return len;
|
|
}
|
|
for (int nextRoute : map.get(station)) {
|
|
if (!set[nextRoute]) {
|
|
nextLevel.add(nextRoute);
|
|
set[nextRoute] = true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
queue = nextLevel;
|
|
len++;
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
}
|