Java实现 LeetCode 815 公交路线（创建关系+BFS）

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.

import java.awt.Point;
class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
       if (S == T) {
            return 0;
        }
        int numsOfBus = routes.length;
        List<List<Integer>> busGraph = new ArrayList<>();
        for (int i = 0; i < numsOfBus; i++) {
            Arrays.sort(routes[i]);
            busGraph.add(new ArrayList<>());
        }
        //把有相同站点的车联系起来
        for (int i = 0; i < numsOfBus; i++) {
            for (int j = i + 1; j < numsOfBus; j++) {
                if (intersect(routes[i], routes[j])) {
                    busGraph.get(i).add(j);
                    busGraph.get(j).add(i);
                }
            }
        }
        Queue<int[]> queue = new LinkedList<>();
        List<Integer> seen = new ArrayList<>();
        List<Integer> targets = new ArrayList<>();
        // 包含起点的加入起始队列，包含目的地的加入目标队列
        // seen用来确保
        for (int i = 0; i < numsOfBus; i++) {
            if (Arrays.binarySearch(routes[i], S) >= 0) {
                seen.add(i);
                queue.add(new int[]{i, 0});
            }
            if (Arrays.binarySearch(routes[i], T) >= 0) {
                targets.add(i);
            }
        }
//BFS走起
        while (!queue.isEmpty()) {                int[] cur = queue.poll();
                int busLine = cur[0];
                int depth = cur[1];
                if (targets.contains(busLine)) {
                    return depth + 1;
                }
                List<Integer> neighbors = busGraph.get(busLine);
                for (int k = 0; k < neighbors.size(); k++) {
                    if (!seen.contains(neighbors.get(k))) {
                        seen.add(neighbors.get(k));
                        queue.add(new int[]{neighbors.get(k), depth + 1});
                    }
                }        }
        return -1;
    }    private boolean intersect(int[] route1, int[] route2) {
        int len1 = route1.length;
        int len2 = route2.length;
        int i = 0;
        int j = 0;
        while (i < len1 && j < len2) {
            if (route1[i] == route2[j]) {
                return true;
            }
            if (route1[i] > route2[j]) {
                j++;
            }
            else
            {
                i++;
            }
        }
        return false;
    }
}