代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一棵由 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/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
我们先根据题目给出的无向树的边,建立一个邻接表 $g$,其中 $g[u]$ 表示顶点 $u$ 的所有相邻顶点。
然后,我们定义以下数据结构:
接下来,我们开始进行广度优先搜索。
在每一轮搜索中,我们每次取出队首元素 $(u, p)$,其中 $u$ 和 $p$ 分别表示当前顶点及其概率。当前顶点 $u$ 的相邻顶点中未被访问过的顶点的个数记为 $cnt$。
在一轮搜索结束后,我们将 $t$ 减少 $1$,然后继续进行下一轮搜索,直到队列为空或者 $t \lt 0$。
最后,若青蛙仍然没有到达目标顶点,那么我们返回 $0$。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 是无向树的顶点数。
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
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 (var 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;
for (; !q.isEmpty() && t >= 0; --t) {
for (int k = q.size(); k > 0; --k) {
var x = q.poll();
int u = x.getKey();
double p = x.getValue();
int cnt = g[u].size() - (u == 1 ? 0 : 1);
if (u == target) {
return cnt * t == 0 ? p : 0;
}
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.offer(new Pair<>(v, p / cnt));
}
}
}
}
return 0;
}
}
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);
}
queue<pair<int, double>> q{{{1, 1.0}}};
bool vis[n + 1];
memset(vis, false, sizeof(vis));
vis[1] = true;
for (; q.size() && t >= 0; --t) {
for (int k = q.size(); k; --k) {
auto [u, p] = q.front();
q.pop();
int cnt = g[u].size() - (u != 1);
if (u == target) {
return cnt * t == 0 ? p : 0;
}
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push({v, p / cnt});
}
}
}
}
return 0;
}
};
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)
}
type pair struct {
u int
p float64
}
q := []pair{{1, 1}}
vis := make([]bool, n+1)
vis[1] = true
for ; len(q) > 0 && t >= 0; t-- {
for k := len(q); k > 0; k-- {
u, p := q[0].u, q[0].p
q = q[1:]
cnt := len(g[u])
if u != 1 {
cnt--
}
if u == target {
if cnt*t == 0 {
return p
}
return 0
}
for _, v := range g[u] {
if !vis[v] {
vis[v] = true
q = append(q, pair{v, p / float64(cnt)})
}
}
}
}
return 0
}
function frogPosition(n: number, edges: number[][], t: number, target: number): number {
const g: number[][] = Array.from({ length: n + 1 }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
}
const q: number[][] = [[1, 1]];
const vis: boolean[] = Array.from({ length: n + 1 }, () => false);
vis[1] = true;
for (; q.length > 0 && t >= 0; --t) {
for (let k = q.length; k > 0; --k) {
const [u, p] = q.shift()!;
const cnt = g[u].length - (u === 1 ? 0 : 1);
if (u === target) {
return cnt * t === 0 ? p : 0;
}
for (const v of g[u]) {
if (!vis[v]) {
vis[v] = true;
q.push([v, p / cnt]);
}
}
}
}
return 0;
}
public class Solution {
public double FrogPosition(int n, int[][] edges, int t, int target) {
List<int>[] g = new List<int>[n + 1];
for (int i = 0; i < n + 1; i++) {
g[i] = new List<int>();
}
foreach (int[] e in edges) {
int u = e[0], v = e[1];
g[u].Add(v);
g[v].Add(u);
}
Queue<Tuple<int, double>> q = new Queue<Tuple<int, double>>();
q.Enqueue(new Tuple<int, double>(1, 1.0));
bool[] vis = new bool[n + 1];
vis[1] = true;
for (; q.Count > 0 && t >= 0; --t) {
for (int k = q.Count; k > 0; --k) {
(var u, var p) = q.Dequeue();
int cnt = g[u].Count - (u == 1 ? 0 : 1);
if (u == target) {
return cnt * t == 0 ? p : 0;
}
foreach (int v in g[u]) {
if (!vis[v]) {
vis[v] = true;
q.Enqueue(new Tuple<int, double>(v, p / cnt));
}
}
}
}
return 0;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。