美文网首页
算法21 Unique Paths II

算法21 Unique Paths II

作者: holmes000 | 来源:发表于2018-01-22 00:05 被阅读0次

    这是之前一个算法的升级版本。
    之前题目:一个机器人在 m × n 的网格中的左上角(在下面示意图中标记 'Start' 的位置)。
    在同一时间点中,机器人只能向下或者向右走。机器人的目标是右下角(用 'Finish' 标记的位置)
    问:有多少种不同的路线?
    本题题目:现在如果我们给栅格中加入了障碍,那会有多少种不同的路径呢?
    在栅格中障碍标记为 1,空格标记为 0。

    例如,
    下面是在 3 × 3 的栅格正中央有一个障碍的情况:
    [
    [0,0,0],
    [0,1,0],
    [0,0,0]
    ]
    不同的路径数是 2。
    注意: m 和 n 都 <= 100.
    思路:
    这题和上一题不同在于有了障碍,所以关键在于对障碍的分析:
    ① 遇到障碍把障碍的值设为 0 代表无法到达这一点
    ② 初始化第一行第一列的时候若遇到障碍,把障碍后面的数也都置为 0(因为后面永远无法到达)

    代码:

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //若传入值为空,则返回0
        if(obstacleGrid.length == 0) return 0;
        //得到行列的长度
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                //若为1则设为 0
                if(obstacleGrid[i][j] == 1)
                    obstacleGrid[i][j] = 0;
                    //把第一个点设为1
                else if(i == 0 && j == 0)
                    obstacleGrid[i][j] = 1;
                    //第一行第一列中若有存在障碍,则它后面的都为0(不可达到)
                else if(i == 0)
                    obstacleGrid[i][j] = obstacleGrid[i][j - 1] * 1;
                else if(j == 0)
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] * 1;
                else
                    //当前位置 = 左边 + 上面
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            }
        }
        return obstacleGrid[rows - 1][cols - 1];
    }
    

    复杂度:空间复杂度O(n),时间复杂度O(raw*cols)

    相关文章

      网友评论

          本文标题:算法21 Unique Paths II

          本文链接:https://www.haomeiwen.com/subject/dllcaxtx.html