最近網上有人列出了曾經在阿里巴巴上過班并離職創業成功的十位大佬,不得不說阿里巴巴確實在向社會輸入人才。
這里面孫彤宇是阿里巴巴初創團隊成員之一,1999 年阿里巴巴剛成立的時候就加入了,2003 年受馬云指派創建淘寶網,后任淘寶網總裁、阿里巴巴副總裁等職,2008 年 3 月離職。
而何小鵬在2004 年聯合創立 UC 優視,打造用戶超 4 億的 UC 瀏覽器,后來被阿里巴巴收購,在后來離職創辦小鵬汽車,也算是在阿里上過班。
--------------下面是今天的算法題--------------
來看下今天的算法題,這題是LeetCode的第1514題:概率最大的路徑,難度是中等。
給你一個由 n 個節點(下標從 0 開始)組成的無向加權圖,該圖由一個描述邊的列表組成,其中 edges[i] = [a, b] 表示連接節點 a 和 b 的一條無向邊,且該邊遍歷成功的概率為 succProb[i] 。
指定兩個節點分別作為起點 start 和終點 end ,請你找出從起點到終點成功概率最大的路徑,并返回其成功概率。
如果不存在從 start 到 end 的路徑,請 返回 0 。只要答案與標準答案的誤差不超過 1e-5 ,就會被視作正確答案。
示例1:
輸入:n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 輸出:0.25000 解釋:從起點到終點有兩條路徑,其中一條的成功概率為 0.2 ,而另一條為 0.5 * 0.5 = 0.25
示例2:
輸入:n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 輸出:0.00000 解釋:節點 0 和 節點 2 之間不存在路徑
2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
每兩個節點之間最多有一條邊
問題分析
這題說的是計算從起始點到終點成功概率的最大路徑,并返回其成功的概率。每條邊都有一個成功的概率值,如果沒有概率值就非常簡單了,我們可以使用BFS或者迪杰斯特拉算法。
每條邊雖然有概率值,但不影響我們計算,這個概率值就相當于邊的權值,但計算的時候不是累加,而是相乘。這里我們可以使用,使用堆優化的方式來解。
剛開始的時候把起始點添加到堆中,然后遍歷堆,堆頂元素出堆之后,計算和它相連的頂點,如果相連的頂點沒有出堆,就把相連的頂點添加到堆中,繼續遍歷堆,直到遇到出堆的元素是終點為止,頂點是否出堆可以用visited數組記錄。
JAVA:
class Pair implements Comparable
{ int v = 0; double p = 0; public Pair(int v, double p) { this.v = v; this.p = p; } @Override public int compareTo(Pair pair) { return Double.compare(pair.p, this.p);// 根據概率從大到小排序。 } } public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) { // 把圖轉化為鄰接表 List [] g = new List[n]; for (int i = 0; i < n; i++) g[i] = new ArrayList<>(); for (int i = 0; i < edges.length; i++) { int u = edges[i][0]; int v = edges[i][1]; double p = succProb[i]; g[u].add(new Pair(v, p)); g[v].add(new Pair(u, p)); } boolean[] visited = newboolean[n];// 標記頂點是否已經出堆。 PriorityQueue pq = new PriorityQueue<>();// 堆 pq.offer(new Pair(start_node, 1));// 起始點添加到堆中 while (!pq.isEmpty()) { Pair cur = pq.poll(); int v = cur.v; double p = cur.p; if (v == end_node) return p; visited[v] = true;// 標記在堆中,頂點在出堆之前是可以多次入堆的。 for (Pair pair : g[v]) { if (!visited[pair.v]) { pq.offer(new Pair(pair.v, pair.p * p)); } } } return0; }
C++:
struct Pair { int v; double p; Pair(int v, double p) : v(v), p(p) {} // 重載比較運算符,根據概率從大到小排序 booloperator<(const Pair &other) const { return p < other.p; } }; public: double maxProbability(int n, vector
> &edges, vector
&succProb, int start_node, int end_node) { // 把圖轉化為鄰接表 vector
g(n); for (int i = 0; i < edges.size(); ++i) { int u = edges[i][0]; int v = edges[i][1]; double p = succProb[i]; g[u].emplace_back(v, p); g[v].emplace_back(u, p); } vector
visited(n, false); // 標記頂點是否已經出堆 priority_queue pq; // 優先隊列(堆) pq.emplace(start_node, 1); // 起始點添加到堆中 while (!pq.empty()) { Pair cur = pq.top(); pq.pop(); int v = cur.v; double p = cur.p; if (v == end_node) return p; visited[v] = true; // 標記在堆中,頂點在出堆之前是可以多次入堆的 for (constauto &pair: g[v]) { if (!visited[pair.v]) { pq.emplace(pair.v, pair.p * p); } } } return0; }
筆者簡介
博哥,真名:王一博,畢業十多年, 作者,專注于 數據結構和算法 的講解,在全球30多個算法網站中累計做題2000多道,在公眾號中寫算法題解800多題,對算法題有自己獨特的解題思路和解題技巧 。
特別聲明:以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布,本平臺僅提供信息存儲服務。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.