Hard

题目描述

给定一个由 n 个顶点组成的无向树，顶点编号为 1 到 n。一只青蛙从顶点 1 开始跳跃。在一秒钟内，青蛙从当前顶点跳到另一个未访问的直接相连顶点。青蛙不能跳回到已访问过的顶点。如果青蛙可以跳到多个顶点，它会以相同的概率随机选择其中一个。否则，当青蛙无法跳到任何未访问的顶点时，它会永远停留在当前顶点。

无向树的边在数组 edges 中给出，其中 edges[i] = [ai, bi] 表示顶点 ai 和 bi 之间存在一条边。

返回在 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 秒后以 1/3 = 0.3333333333333333 的概率跳到顶点 7。

约束条件:

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

解题思路

这是一道概率动态规划问题，需要使用DFS来模拟青蛙的跳跃过程。

思路分析：

  1. 建图：首先根据edges数组构建邻接表表示的无向树。

  2. DFS核心思想：使用深度优先搜索，参数包括当前顶点、剩余时间和到达当前顶点的概率。

  3. 关键判断：

    • 如果当前时间正好等于t且当前顶点为target，返回概率
    • 如果时间用完但不在target，返回0
    • 如果当前顶点没有未访问的邻居，青蛙会停留，需要检查是否为target

  4. 概率计算：从当前顶点跳到每个未访问邻居的概率是 1/未访问邻居数量。

  5. 剪枝优化：

    • 如果到达target的距离大于剩余时间，直接返回0
    • 如果已经到达target但还有剩余时间，只有当target是叶节点时才能停留

算法步骤：

  • 构建邻接表
  • 从顶点1开始DFS，初始概率为1.0
  • 对于每个顶点，计算其未访问的邻居数量
  • 递归计算到达target的概率

代码实现

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<vector<int>> graph(n + 1);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        vector<bool> visited(n + 1, false);
        return dfs(graph, visited, 1, t, target, 1.0);
    }
    
private:
    double dfs(vector<vector<int>>& graph, vector<bool>& visited, int curr, int time, int target, double prob) {
        visited[curr] = true;
        
        int unvisited = 0;
        for (int neighbor : graph[curr]) {
            if (!visited[neighbor]) {
                unvisited++;
            }
        }
        
        if (time == 0) {
            return curr == target ? prob : 0.0;
        }
        
        if (unvisited == 0) {
            return curr == target ? prob : 0.0;
        }
        
        if (curr == target) {
            return 0.0;
        }
        
        double result = 0.0;
        for (int neighbor : graph[curr]) {
            if (!visited[neighbor]) {
                result += dfs(graph, visited, neighbor, time - 1, target, prob / unvisited);
            }
        }
        
        visited[curr] = false;
        return result;
    }
};

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        from collections import defaultdict
        
        graph = defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        visited = [False] * (n + 1)
        
        def dfs(curr, time, prob):
            visited[curr] = True
            
            unvisited_neighbors = [neighbor for neighbor in graph[curr] if not visited[neighbor]]
            unvisited_count = len(unvisited_neighbors)
            
            if time == 0:
                visited[curr] = False
                return prob if curr == target else 0.0
            
            if unvisited_count == 0:
                visited[curr] = False
                return prob if curr == target else 0.0
            
            if curr == target:
                visited[curr] = False
                return 0.0
            
            result = 0.0
            for neighbor in unvisited_neighbors:
                result += dfs(neighbor, time - 1, prob / unvisited_count)
            
            visited[curr] = False
            return result
        
        return dfs(1, t, 1.0)

public class Solution {
    public double FrogPosition(int n, int[][] edges, int t, int target) {
        List<int>[] graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        bool[] visited = new bool[n + 1];
        return DFS(graph, visited, 1, t, target, 1.0);
    }
    
    private double DFS(List<int>[] graph, bool[] visited, int curr, int time, int target, double prob) {
        visited[curr] = true;
        
        int unvisited = 0;
        foreach (int neighbor in graph[curr]) {
            if (!visited[neighbor]) {
                unvisited++;
            }
        }
        
        if (time == 0) {
            visited[curr] = false;
            return curr == target ? prob : 0.0;
        }
        
        if (unvisited == 0) {
            visited[curr] = false;
            return curr == target ? prob : 0.0;
        }
        
        if (curr == target) {
            visited[curr] = false;
            return 0.0;
        }
        
        double result = 0.0;
        foreach (int neighbor in graph[curr]) {
            if (!visited[neighbor]) {
                result += DFS(graph, visited, neighbor, time - 1, target, prob / unvisited);
            }
        }
        
        visited[curr] = false;
        return result;
    }
}

var frogPosition = function(n, edges, t, target) {
    const graph = Array(n + 1).fill(null).map(() => []);
    
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    const visited = new Set([1]);
    const queue = [[1, 1.0, 0]]; // [vertex, probability, time]
    
    while (queue.length > 0) {
        const [vertex, prob, time] = queue.shift();
        
        const unvisitedNeighbors = graph[vertex].filter(neighbor => !visited.has(neighbor));
        
        if (vertex === target) {
            if (time === t || unvisitedNeighbors.length === 0) {
                return prob;
            }
            return 0;
        }
        
        if (time === t) continue;
        
        if (unvisitedNeighbors.length === 0) {
            if (vertex === target) return prob;
            continue;
        }
        
        const nextProb = prob / unvisitedNeighbors.length;
        
        for (const neighbor of unvisitedNeighbors) {
            visited.add(neighbor);
            queue.push([neighbor, nextProb, time + 1]);
        }
    }
    
    return 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
最优解法O(n)O(n)

说明：

  • 时间复杂度： O(n)，在最坏情况下需要遍历所有节点一次
  • 空间复杂度： O(n)，主要用于存储图的邻接表和递归调用栈

相关题目