目录

1377:T 秒后青蛙的位置(1823 分)

力扣第 179 场周赛第 4 题

题目

给你一棵由 n 个顶点组成的无向树,顶点编号从 1n。青蛙从 顶点 1 开始起跳。规则如下:

  • 在一秒内,青蛙从它所在的当前顶点跳到另一个 未访问 过的顶点(如果它们直接相连)。
  • 青蛙无法跳回已经访问过的顶点。
  • 如果青蛙可以跳到多个不同顶点,那么它跳到其中任意一个顶点上的机率都相同。
  • 如果青蛙不能跳到任何未访问过的顶点上,那么它每次跳跃都会停留在原地。

无向树的边用数组 edges 描述,其中 edges[i] = [ai, bi] 意味着存在一条直接连通 aibi 两个顶点的边。

返回青蛙在 t 秒后位于目标顶点 target 上的概率。与实际答案相差不超过 10-5 的结果将被视为正确答案。

示例 1:

输入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4
输出:0.16666666666666666
解释:上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳,第 1 秒 有 1/3 的概率跳到顶点 2 ,然后第 2 秒 有 1/2 的概率跳到顶点 4,因此青蛙在 2 秒后位于顶点 4 的概率是 1/3 * 1/2 = 1/6 = 0.16666666666666666 。

示例 2:

输入:n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 1, target = 7
输出:0.3333333333333333
解释:上图显示了青蛙的跳跃路径。青蛙从顶点 1 起跳,有 1/3 = 0.3333333333333333 的概率能够 1 秒 后跳到顶点 7 。

提示:

  • 1 <= n <= 100
  • edges.length == n - 1
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • 1 <= t <= 50
  • 1 <= target <= n

分析

  • 遍历并维护到达当前节点的时间和概率即可
  • 还可以维护概率的倒数 p,最后返回 1/p,避免浮点数误差

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        g = [set() for _ in range(n+1)]
        for u,v in edges:
            g[u].add(v)
            g[v].add(u)
        sk = [(0,1,1)]
        while sk:
            w,u,p = sk.pop()
            if u==target:
                return 0 if w<t and g[u] else 1/p
            if w==t:
                continue
            for v in g[u]:
                sk.append((w+1,v,p*len(g[u])))
                g[v].remove(u)
        return 0

0 ms