Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-06-30 01:08:18
https://leetcode.com/problems/path-with-maximum-probability/description/
1514. Path with Maximum Probability
给你一个大小为 n 的无向图资讯,阵列 edges[] 表示边关系,succProb[] 表示边的机
率权重,路径经过时需要乘以该权重,求出从 start 走到 end 的路径,他的最终权重必
需是最高,走不到则返回0。
Example 1:
https://assets.leetcode.com/uploads/2019/09/20/1558_ex1.png
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start =
0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability
of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
Example 2:
https://assets.leetcode.com/uploads/2019/09/20/1558_ex2.png
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start =
0, end = 2
Output: 0.30000
Example 3:
https://assets.leetcode.com/uploads/2019/09/20/1558_ex3.png
Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.
思路:
1.图形的最短路径问题要先想到 BFS,但是因为每个边的权重不同所以不能用 Queue 去
做,第一个到达终点的未必是最短路径,所以我们改用 maxHeap 来让每次都从机率最
大的路径开始计算。
2.然后额外加入一个表纪录之前算过的每个点的最大机率,只有新的机率使旧的变高才
更新。
3.如果最后到达不了 end 就返回 false。
Java Code:
作者: Firstshadow (IamCatづミ'_'ミづ)   2023-06-30 01:10:00
大师
作者: ririoshi (角落住民)   2023-06-30 01:14:00
大师
作者: ILoveErr (英梨梨我老婆)   2023-06-30 01:14:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com