T 秒后青蛙的位置【LC1377】
给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n。青蛙从 顶点 1 开始起跳。规则如下：
- 在一秒内，青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点（如果它们直接相连）。
- 青蛙无法跳回已经访问过的顶点。
- 如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。
- 如果青蛙不能跳到任何未访问过的顶点上，那么它每次跳跃都会停留在原地。
无向树的边用数组 edges 描述，其中 edges[i] = [ai, bi] 意味着存在一条直接连通 ai 和 bi 两个顶点的边。
返回青蛙在 t 秒后位于目标顶点 target 上的概率。与实际答案相差不超过 10-5 的结果将被视为正确答案。
今天BFS模拟了一下
- 思路
题意可以转化为寻找根节点至target节点的路径，路径边数需要小于等于t。而当到达target节点时，target节点是否是叶子节点，时间t是否还有剩余，需要分情况讨论： - 当时间没有剩余，无论
target节点是否是叶子节点，概率为固定值（1/(a∗b∗c)，每次可选择的节点的乘积的倒数） - 当时间有剩余，
target节点是叶子节点时，概率也为固定值（1/(a∗b∗c)），剩余的时间只能在target节点反复横挑
- 当时间有剩余，
target节点不是叶子节点时，概率为0，剩余的时间只能向下移动，不会停留在target节点
因此，可以使用BFS或者DFS搜索时间t秒后节点移动至target节点的概率是多少
BFS
2023/5/24
- 实现
- 首先构建邻接矩阵，由于下标从0开始，将节点序号整体减1
- 然后使用布尔数组记录该节点是否访问过
- 然后使用队列进行BFS搜索，队列中存储节点标号及到达该节点时的概率
- 由于该图是一颗树，不存在环，那么除了根节点之外其他节点下一跳的选择是邻接表中节点数量-1；而根节点即为邻接表中节点数量
- 当当前节点为目标节点时，分情况返回概率
- 如果当前节点不为目标节点，那么计算概率，并将下一跳添加至队列中
- 最后如果不存在目标节点，那么返回0
class Solution { public double frogPosition(int n, int[][] edges, int t, int target) { // 树->寻找根节点到target-1节点的路径，路径边数小于等于t // 等于t时，概率为a*b*c.. // 小于t时，target-1节点为叶子节点，概率为a*b*c.. // 小于t时，target-1节点不为叶子节点，那么必须向下走，概率为0 boolean[] vis = new boolean[n]; vis[0] = true; Deque<double[]> queue = new LinkedList<>(); queue.addLast(new double[]{0, 1}); // 邻接表 List<Integer>[] g = new List[n]; for (int i = 0; i < n; i++){ g[i] = new ArrayList<>(); } for (int[] edge : edges){ int u = edge[0] - 1, v = edge[1] - 1; g[u].add(v); g[v].add(u); } double res = 0; while(t >= 0 && !queue.isEmpty()){ t--; int size = queue.size(); for (int i = 0; i < size; i++){ double[] data = queue.pollFirst(); int u = (int)data[0]; double p = data[1]; int num = g[u].size() - (u == 0 ? 0 : 1); if (u == target - 1){ if (num == 0 || t < 0){ return p; }else{ return 0; } } if (num == 0) continue; p *= 1.0 / num; for (int v :g[u]){ if (vis[v]) continue; queue.addLast(new double[]{v, p}); vis[v] = true; } } } return 0; } }
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
DFS
- 自顶向下
一边「递」，一边把儿子个数 c乘起来，如果能在第t秒到达target，或者小于t秒到达target且target是叶子节点（此时每次跳跃都会停留在原地），那么就记录答案为乘积的倒数，同时返回一个布尔值表示递归结束。
class Solution { private double ans; public double frogPosition(int n, int[][] edges, int t, int target) { List<Integer>[] g = new ArrayList[n + 1]; Arrays.setAll(g, e -> new ArrayList<>()); g[1].add(0); // 减少额外判断的小技巧 for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); // 建树 } dfs(g, target, 1, 0, t, 1); return ans; } private boolean dfs(List<Integer>[] g, int target, int x, int fa, int leftT, long prod) { // t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地） if (x == target && (leftT == 0 || g[x].size() == 1)) { ans = 1.0 / prod; return true; } if (x == target || leftT == 0) return false; for (int y : g[x]) // 遍历 x 的儿子 y if (y != fa && dfs(g, target, y, x, leftT - 1, prod * (g[x].size() - 1))) return true; // 找到 target 就不再递归了 return false; // 未找到 target } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/frog-position-after-t-seconds/solutions/2281408/dfs-ji-yi-ci-you-qu-de-hack-by-endlessch-jtsr/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
自底向上
找到 target 后，在「归」的过程中做乘法。
class Solution { public double frogPosition(int n, int[][] edges, int t, int target) { List<Integer>[] g = new ArrayList[n + 1]; Arrays.setAll(g, e -> new ArrayList<>()); g[1].add(0); // 减少额外判断的小技巧 for (var e : edges) { int x = e[0], y = e[1]; g[x].add(y); g[y].add(x); // 建树 } long prod = dfs(g, target, 1, 0, t); return prod != 0 ? 1.0 / prod : 0; } private long dfs(List<Integer>[] g, int target, int x, int fa, int leftT) { // t 秒后必须在 target（恰好到达，或者 target 是叶子停在原地） if (leftT == 0) return x == target ? 1 : 0; if (x == target) return g[x].size() == 1 ? 1 : 0; for (int y : g[x]) { // 遍历 x 的儿子 y if (y != fa) { // y 不能是父节点 long prod = dfs(g, target, y, x, leftT - 1); // 寻找 target if (prod != 0) return prod * (g[x].size() - 1); // 乘上儿子个数，并直接返回 } } return 0; // 未找到 target } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/frog-position-after-t-seconds/solutions/2281408/dfs-ji-yi-ci-you-qu-de-hack-by-endlessch-jtsr/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
