专治BFS不熟, 常练这道题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }
        // Store for a given stop, which route(s) contain such stop
        // This means from this stop, all the stops in the routes that contain such stop
        // can be arrived by taking one bus
        Map<Integer, List<Integer>> stopRoutesMap = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopRoutesMap.putIfAbsent(stop, new ArrayList<>());
                stopRoutesMap.get(stop).add(i);
            }
        }
        Queue<Integer> stopQueue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        boolean[] visitedRoutes = new boolean[routes.length];
        int busNum = 0;
        stopQueue.offer(source);
        visited.add(source);
        while (!stopQueue.isEmpty()) {
            // Currently the queue contains all the stops that we can arrive with busNum
            // buses
            int size = stopQueue.size();
            for (int i = 0; i < size; i++) {
                int currStop = stopQueue.poll();
                List<Integer> routesInvolved = stopRoutesMap.get(currStop);
                for (Integer routeNum : routesInvolved) {
                    if (visitedRoutes[routeNum]) {
                        continue;
                    }
                    int[] stopOfCurrRoute = routes[routeNum];
                    for (int stop : stopOfCurrRoute) {
                        if (visited.add(stop)) {
                            if (stop == target) {
                                return busNum + 1;
                            } else {
                                stopQueue.offer(stop);
                            }
                        }
                    }
                    visitedRoutes[routeNum] = true;
                }
            }
            // Right now, the queue contains all the stops that need busNum + 1 buses to
            // arrive
            // so we update busNum now
            busNum += 1;
        }
        return -1;
    }
}

BFS练手项目. 看了lee215大神的讲解, 大概明白意思后自己写出来百分之99, 差那百分之1就是没有把visitedRoutes给考虑到. 这道题完美套用我之前打标签的思路, 我们BFS前要知道queue里面装的元素对应的标签是什么, BFS一次之后queue里装的元素对应的标签是什么.

现在我来说一下思路. 从source开始, 我们此时不用乘车, 因此初始化busNum为0. 凡是在给定的routes中包含source的, 那么我们乘坐一辆公交就可以到达. 然后再从所有这些一辆公交可以到达的站, 分别看每一个站又有哪些routes包含它, 那么包含它routes的站从source需要两个公交能到. 需要注意的是, 到过的站我们要标记, 否则到达这些站需要的bus数目就是不对的. 还有需要注意的是, 我们走过的routes也要标记. 比如route 1包含source, source通过route1可以到达a, a通过route2又能到达b, 但source不能直接到b. b通过route3又能到达route1, 假设route3和route1的交叉点为q. 当我们走到q的时候, 我们会把穿过q的所有routes包含的那些之前没有被visited过的stops添加到queue中. 当然我们也会遍历route1, 但是真的有必要遍历route1嘛? route1里面的所有的stops在之前的BFS中都被添加到了visited里面, 我们遍历一遍是不会添加任何stops进queue的. 因此这是无效功. 综上我们也要记录哪些routes被走过了.

以上.

假设stop的个数是n, route的个数是m.
时间复杂度: 首先所有的stop会被visit一次来构成map. 然后BFS的时候每个stop也只会被visit一次. 那么时间复杂度就是O(n).
空间复杂度: map的话我们是一共n个entry. 每个stop最多可能有m个route都穿过. 这就是O(m * n). 我们BFS的时候, 存经过某个stop所有没被visited的routes的stops. 也就是m * n个(有可能source是在所有routes的交叉口).