What is the main algorithm to solve the 'Frog Position After T Seconds' problem?

The main algorithm involves depth-first search (DFS) to explore the tree and calculate the probability of the frog being on the target vertex after t seconds, with memoization to optimize performance.

How can I optimize my solution for the 'Frog Position After T Seconds' problem?

You can optimize your solution by using memoization to store intermediate results and avoid redundant calculations. This reduces the time complexity of the DFS traversal.

What is the time complexity of the solution for the 'Frog Position After T Seconds' problem?

The time complexity of the DFS approach with memoization is O(n * t), where n is the number of vertices and t is the number of seconds.

Can the 'Frog Position After T Seconds' problem be solved without using DFS?

While DFS is the most natural approach for this problem, other techniques such as breadth-first search (BFS) can also be used, but DFS is typically more efficient for tree traversal.

What are common mistakes to avoid when solving the 'Frog Position After T Seconds' problem?

Common mistakes include not properly handling the case where the frog stays on a vertex, failing to divide the probability when there are multiple possible jumps, and not using memoization to optimize the DFS approach.

#1377

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

T 秒后青蛙的位置

给你一棵由 n 个顶点组成的无向树，顶点编号从 1 到 n 。青蛙从顶点 1 开始起跳。规则如下：在一秒内，青蛙从它所在的当前顶点跳到另一个未访问过的顶点（如果它们直接相连）。青蛙无法跳回已经访问过的顶点。如果青蛙可以跳到多个不同顶点，那么它跳到其中任意一个顶点上的机率都相同。如果青蛙…

树深度优先搜索广度优先搜索图

题目描述

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

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

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

返回青蛙在 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 <= a_i, b_i <= n
1 <= t <= 50
1 <= target <= n

lightbulb

解题思路

方法一：BFS

我们先根据题目给出的无向树的边，建立一个邻接表 $g$ ，其中 $g[u]$ 表示顶点 $u$ 的所有相邻顶点。

然后，我们定义以下数据结构：

队列 $q$ ，用于存储每一轮搜索的顶点及其概率，初始时 $q = [(1, 1.0)]$ ，表示青蛙在顶点 $1$ 的概率为 $1.0$ ；
数组 $vis$ ，用于记录每个顶点是否被访问过，初始时 $vis[1] = true$ ，其余元素均为 $false$ 。

接下来，我们开始进行广度优先搜索。

在每一轮搜索中，我们每次取出队首元素 $(u, p)$ ，其中 $u$ 和 $p$ 分别表示当前顶点及其概率。当前顶点 $u$ 的相邻顶点中未被访问过的顶点的个数记为 $cnt$ 。

如果 $u = target$ ，说明青蛙已经到达目标顶点，此时我们判断青蛙是否在 $t$ 秒到达目标顶点，或者不到 $t$ 秒到达目标顶点但是无法再跳跃到其它顶点（即 $t=0$ 或者 $cnt=0$ ）。如果是，则返回 $p$ ，否则返回 $0$ 。
如果 $u \neq target$ ，那么我们将概率 $p$ 均分给 $u$ 的所有未被访问过的相邻顶点，然后将这些顶点加入队列 $q$ 中，并且将这些顶点标记为已访问。

在一轮搜索结束后，我们将 $t$ 减少 $1$ ，然后继续进行下一轮搜索，直到队列为空或者 $t \lt 0$ 。

最后，若青蛙仍然没有到达目标顶点，那么我们返回 $0$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $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

class Solution:
    def frogPosition(
        self, n: int, edges: List[List[int]], t: int, target: int
    ) -> float:
        g = defaultdict(list)
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        q = deque([(1, 1.0)])
        vis = [False] * (n + 1)
        vis[1] = True
        while q and t >= 0:
            for _ in range(len(q)):
                u, p = q.popleft()
                cnt = len(g[u]) - int(u != 1)
                if u == target:
                    return p if cnt * t == 0 else 0
                for v in g[u]:
                    if not vis[v]:
                        vis[v] = True
                        q.append((v, p / cnt))
            t -= 1
        return 0

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate can efficiently solve the problem using DFS with memoization.
question_mark
The candidate can explain how to handle the random jumps in the tree graph.
question_mark
The candidate can discuss edge cases, such as when the frog cannot move or stays on a vertex.

warning

常见陷阱

外企场景

error
Forgetting to account for the case where the frog stays on the same vertex after all possible moves are visited.
error
Not properly dividing the probability when multiple vertices are available for the frog to jump to.
error
Failing to optimize the DFS approach with memoization, leading to excessive recomputation.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The frog jumps with a probability to any of the connected vertices, including cases where some vertices are visited earlier.
arrow_right_alt
The tree can be directed, where the frog can only jump in one direction based on the tree structure.
arrow_right_alt
Change the problem to ask for the probability of being on a vertex after a specific number of jumps, not time.

help

常见问题

外企场景

继续练习

#1361 验证二叉树 #2368 受限条件下可到达节点的数目 #1319 连通网络的操作次数