LC.P1377[T秒后青蛙的位置]

方法一：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
class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            g[u].add(v);
            g[v].add(u);
        }
        Deque<Pair<Integer, Double>> queue = new ArrayDeque<>();
        queue.offer(new Pair<>(1, 1.0));
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        while (!queue.isEmpty() && t >= 0) {
            int size = queue.size();
            while (size-- > 0) {
                var cur = queue.poll();
                int u = cur.key;
                double p = cur.value;
                int cnt = g[u].size() - (u == 1 ? 0 : 1);
                if (u == target) {
                    // 如果到达目标顶点，需要判断
                    // 1.是否在t秒到达目标顶点
                    // 2.小于t秒时到达目标顶点，但无法再跳跃至其他顶点
                    return cnt * t == 0 ? p : 0;
                }
                for (int v : g[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.offer(new Pair<>(v, p / cnt));
                    }
                }
            }
            --t;
        }
        return 0;
    }

    private static class Pair<K, V> {
        K key;
        V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：优化计算结果

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
class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            g[u].add(v);
            g[v].add(u);
        }
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{1, 1});
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        while (!queue.isEmpty() && t >= 0) {
            int size = queue.size();
            while (size-- > 0) {
                var cur = queue.poll();
                int u = cur[0], p = cur[1];
                int cnt = g[u].size() - (u == 1 ? 0 : 1);
                if (u == target) {
                    // 如果到达目标顶点，需要判断
                    // 1.是否在t秒到达目标顶点
                    // 2.小于t秒时到达目标顶点，但无法再跳跃至其他顶点
                    return cnt * t == 0 ? 1.0 / p : 0;
                }
                for (int v : g[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.offer(new int[]{v, p * cnt});
                    }
                }
            }
            --t;
        }
        return 0;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法三：减少特判

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
class Solution {
    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            g[u].add(v);
            g[v].add(u);
        }
        // 给1节点添加一个0号节点，避免特判 n = 1 的情况
        g[1].add(0);
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{1, 1});
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        while (!queue.isEmpty() && t >= 0) {
            int size = queue.size();
            while (size-- > 0) {
                var cur = queue.poll();
                int u = cur[0], p = cur[1];
                int cnt = g[u].size() - 1;
                if (u == target) {
                    // 如果到达目标顶点，需要判断
                    // 1.是否在t秒到达目标顶点
                    // 2.小于t秒时到达目标顶点，但无法再跳跃至其他顶点
                    return cnt * t == 0 ? 1.0 / p : 0;
                }
                for (int v : g[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        queue.offer(new int[]{v, p * cnt});
                    }
                }
            }
            --t;
        }
        return 0;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$