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

向右看齐 2023-03-13 02:07 14阅读 0赞

## 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;
        }
    }