题目描述
n个顶点构成了无向树
顶点编号从1到n
给了跳跃规则（1）跳相临边（2）不往回跳（3）多个选择概率相同（4）叶子结点时候就停下来
问t秒后跳到目标顶点target上的概率？
基本分析
- 怎么保证不往回跳？dfs时候传入父节点参数
- dfs怎么定义？当前在x，父节点是fa，步数是step时候到达当前节点的概率？
代码
class Solution:
def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
g = defaultdict(list)
for x, y in edges:
g[x].append(y)
g[y].append(x)
# 当前概率，当前节点，传入父节点，步骤
def dfs(p, x, fa, step):
if step == t:
if x == target:
return p
return 0.0
# 除了跟节点外，子节点个数都要-1
cnt_child = len(g[x]) - 1 if x != 1 else len(g[x])
# 子节点
if cnt_child == 0:
if x == target:
return p
return 0
# 其他情况
# ans是左右分支中的最大值
ans = 0
for y in g[x]:
if y != fa:
ans = max(ans, dfs(p * 1.0 / cnt_child, y, x, step + 1))
return ans
return dfs(1, 1, -1, 0)
总结
- 需要再消化下
基本分析
- 怎么保证不往回跳？同样在状态的定义时，传入这个参数
- bfs什么时候返回？时间到找到了target或者到了target且不能走了
- 怎么控制bfs的流程？存在q+时间<=t
代码
class Solution:
def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
g = defaultdict(list)
for x, y in edges:
g[x].append(y)
g[y].append(x)
step = 0
q = deque([(1, -1, 1.0)])
while q and step <= t:
for _ in range(len(q)):
# 当前节点，父节点，概率
x, fa, p = q.popleft()
if x == target and step == t:
return p
chd_cnt = len(g[x]) - 1
# 如果是1多减了一个，补回来
if fa == -1:
chd_cnt += 1
# 到达了叶子结点
if chd_cnt == 0:
if x == target:
return p
continue
# 继续传
for y in g[x]:
if y != fa:
q.append((y, x, 1.0 * p / chd_cnt))
step += 1
return 0
总结
- 和dfs的不同？在没有找到的情况下，不返回