Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/30 01:08)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串357/719 (看更多)

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： ------------------------------------------------------- class Solution { public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { List<double[]>[] graph = new ArrayList[n]; for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); } for (int i = 0; i < edges.length; i++) { int[] edge = edges[i]; int v = edge[0]; int u = edge[1]; double p = succProb[i]; graph[v].add(new double[] {(double) u, p}); graph[u].add(new double[] {(double) v, p}); } PriorityQueue<double[]> maxHeap = new PriorityQueue<>( Comparator.comparingDouble(d -> -d[1])); maxHeap.offer(new double[] {start, 1.0}); double[] rate = new double[n]; Arrays.fill(rate, -1); while (!maxHeap.isEmpty()) { double[] curr = maxHeap.poll(); int currId = (int) curr[0]; double currRate = curr[1]; if (currId == end) { return currRate; } if (currId != start && currRate < rate[currId]) { continue; } for (double[] next : graph[currId]) { int nextId = (int) next[0]; double nextRate = next[1] * currRate; if (nextRate > rate[nextId]) { rate[nextId] = nextRate; maxHeap.offer(new double[] {(double) nextId, nextRate}); } } } return 0; } } ------------------------------------------------------- 晚安 -- https://i.imgur.com/tdaniED.jpg