X

LEETCODE 1514. Path with Maximum Probability 解题思路分析

题目大意:

概率最大的路径

给你一个由 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],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出:0.30000

示例 3:

输入: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
  • 每两个节点之间最多有一条边

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1514

解题思路分析:

这是一道图形题目。与树形结构类似,遇到图形结构我们通常也要想到使用dfs或者bfs解题。而本题求解的是最优路径,这实际上等同于寻找最短路径,对于这类问题,我在bfs算法讲解的文章中提到过,这是bfs广度优先搜索的长项,因此本题需使用到BFS。

另外,由于图形结构会出现环路以及多个节点指向同一节点的可能,这样一来,对于某个节点,可能会被多次访问,从而导致代码多次重复执行,因此我们需要使用一个访问数组来记录已经访问过的节点。而本题略有不同,因为本题的边带有权重,这会导致从不同边或路径访问到当前节点时总的权重乘积(成功概率)会不同,因此对于访问节点的使用需要做一些改变,数组中存储的是从起始点到当前节点的所有路径中,最大的概率值,当再次访问到当前节点时,如果当前的概率小于等于访问数组中的值,那么不再继续。反之,更新数组中的最大值,继续遍历当前路径。bfs遍历时,如果当前节点等于目标节点,用当前的概率更新全局最大概率,并且当前路径不再继续向下遍历。

实现代码:

public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    List<double[]>[] map=new ArrayList[n]; // 构建图形结构
    for(int i=0;i<edges.length;i++){
        int[]edge=edges[i];
        if(map[edge[0]]==null) map[edge[0]]=new ArrayList<>();
        map[edge[0]].add(new double[]{edge[1], succProb[i]});
        if(map[edge[1]]==null) map[edge[1]]=new ArrayList<>();
        map[edge[1]].add(new double[]{edge[0], succProb[i]});
    }
    // 记录访问过的节点
    // memo[i]代表从起始节点到i节点间的最大概率
    double[] memo=new double[n];
    Queue<double[]> q=new LinkedList<>();  // bfs用的queue
    // 将起始节点,加入Queue,1d代表从start到start的概率为1
    q.offer(new double[]{start,1d});
    memo[start]=1; // 从start到start的概率为1
    double res=0; // 返回结果
    while(q.size()>0){ // 以下为标准bfs
        double[] d=q.poll(); // 取出一个节点
        int node=(int)d[0]; // 节点下标
        double sp=d[1]; // 当前路径走到该节点时的概率
        if(node==end){ // 如果当前节点为目标节点
            res=Math.max(res,sp); // 用当前概率全局更新最大概率
            continue; // 结束当前路径
        }
        // 如果当前路径没有其他相邻节点,跳过
        if(map[node]==null) continue;
        // 循环当前节点的所有相邻节点
        for(double[] next : map[node]){
            int nextNode=(int)next[0]; // 相邻接点下标
            double nextSp = sp*next[1]; // 当前路径走到相邻接点时的概率
            if(nextSp>memo[nextNode]){ // 如果概率大于数组的概率
                memo[nextNode]=nextSp; // 更新到相邻接点的最大概率
                q.offer(new double[]{nextNode, nextSp}); // 走到下一个节点
            }
        }
    }
    return res;
}

本题解法执行时间为60ms。

Runtime: 60 ms, faster than 86.42% of Java online submissions for Path with Maximum Probability.

Memory Usage: 103.8 MB, less than 100.00% of Java online submissions for Path with Maximum Probability.

另外,刷题时有小伙伴问本题为什么不可以使用dfs求解?这里我也贴一下dfs的代码,我尝试提交了一下,不出所料果然TLE。

double[] memo;
double res=0;
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
    List<double[]>[] map=new ArrayList[n];
    memo=new double[n];
    memo[start]=1;
    for(int i=0;i<edges.length;i++){
        int[]edge=edges[i];
        if(map[edge[0]]==null) map[edge[0]]=new ArrayList<>();
        map[edge[0]].add(new double[]{edge[1], succProb[i]});
        if(map[edge[1]]==null) map[edge[1]]=new ArrayList<>();
        map[edge[1]].add(new double[]{edge[0], succProb[i]});
    }
    dfs(map,start,end, 1);
    return res;
}

void dfs(List<double[]>[] map,int current,int end, double sp){
    if(current==end){
        res=Math.max(res, sp);
        return;
    }
    if(map[current]==null) return;
    for(double[] next:map[current]){
        int nextNode=(int)next[0];
        double nextSp=next[1]*sp;
        if(nextSp>memo[nextNode]){
            memo[nextNode]=nextSp;
            dfs(map, nextNode, end, nextSp);
        }
    }
}

这里简单分析一下,dfs的代码逻辑与bfs完全一致,但结果是超时,而bfs则不会。所以bfs到底优秀在哪里?对于这个问题我们在bfs算法讲解的文章中也提到过。dfs是深度优先搜索,即一条路径一条路径的遍历,因此要想找到最优解,必须遍历完所有路径才行。而bfs则不然,使用Queue的目的是逐层(距离起始节点的距离)的遍历节点,遍历的深度为最优路径的长度。除非最优路径是最长的那条路径,否则时间复杂度肯定小于dfs。举个例子,比如一共有10条路径,其中9条路径的长度为5,1条路径的长度为100亿。使用dfs我们无论如何也要遍历一遍长度为100亿的那一条。而bfs则不同,一旦我们找到了最优解,bfs就会停止在当前层数。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1514-path-with-maximum-probability-解题思路分析/
Categories: leetcode
kwantong:

View Comments (2)