Skip to content

Latest commit

 

History

History
229 lines (192 loc) · 6.69 KB

README.md

File metadata and controls

229 lines (192 loc) · 6.69 KB
Raw

1377. T 秒后青蛙的位置

English Version

题目描述

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

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

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

返回青蛙在 t 秒后位于目标顶点 target 上的概率。

 

示例 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

解法

方法一：BFS

Python3

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()
                nxt = [v for v in g[u] if not vis[v]]
                if u == target and (not nxt or t == 0):
                    return p
                for v in nxt:
                    vis[v] = True
                    q.append((v, p / len(nxt)))
            t -= 1
        return 0

Java

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[] e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        Deque<Pair<Integer, Double>> q = new ArrayDeque<>();
        q.offer(new Pair<>(1, 1.0));
        boolean[] vis = new boolean[n + 1];
        vis[1] = true;
        while (!q.isEmpty() && t >= 0) {
            for (int k = q.size(); k > 0; --k) {
                Pair<Integer, Double> x = q.poll();
                int u = x.getKey();
                double p = x.getValue();
                List<Integer> nxt = new ArrayList<>();
                for (int v : g[u]) {
                    if (!vis[v]) {
                        nxt.add(v);
                        vis[v] = true;
                    }
                }
                if (u == target && (nxt.isEmpty() || t == 0)) {
                    return p;
                }
                for (int v : nxt) {
                    q.offer(new Pair<>(v, p / nxt.size()));
                }
            }
            --t;
        }
        return 0;
    }
}

C++

class Solution {
public:
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        vector<vector<int>> g(n + 1);
        for (auto& e : edges) {
            int u = e[0], v = e[1];
            g[u].push_back(v);
            g[v].push_back(u);
        }
        typedef pair<int, double> pid;
        queue<pid> q;
        q.push({1, 1.0});
        vector<bool> vis(n + 1);
        vis[1] = true;
        while (!q.empty() && t >= 0) {
            for (int k = q.size(); k; --k) {
                auto x = q.front();
                q.pop();
                int u = x.first;
                double p = x.second;
                vector<int> nxt;
                for (int v : g[u]) {
                    if (!vis[v]) {
                        vis[v] = true;
                        nxt.push_back(v);
                    }
                }
                if (u == target && (t == 0 || nxt.empty())) return p;
                for (int v : nxt) q.push({v, p / nxt.size()});
            }
            --t;
        }
        return 0;
    }
};

Go

type pid struct {
	x int
	p float64
}

func frogPosition(n int, edges [][]int, t int, target int) float64 {
	g := make([][]int, n+1)
	for _, e := range edges {
		u, v := e[0], e[1]
		g[u] = append(g[u], v)
		g[v] = append(g[v], u)
	}
	q := []pid{pid{1, 1.0}}
	vis := make([]bool, n+1)
	vis[1] = true
	for len(q) > 0 && t >= 0 {
		for k := len(q); k > 0; k-- {
			x := q[0]
			q = q[1:]
			u, p := x.x, x.p
			var nxt []int
			for _, v := range g[u] {
				if !vis[v] {
					vis[v] = true
					nxt = append(nxt, v)
				}
			}
			if u == target && (len(nxt) == 0 || t == 0) {
				return p
			}
			for _, v := range nxt {
				q = append(q, pid{v, p / float64(len(nxt))})
			}
		}
		t--
	}
	return 0
}

...