Leetcode算法Java全解答-- 63. 不同路径 II

曾经终败给现在 2022-04-04 04:31 192阅读 0赞

# Leetcode算法Java全解答-- 63. 不同路径 II #

### 文章目录 ###

*  Leetcode算法Java全解答-- 63. 不同路径 II
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:
    
    输入:
    [
    [0,0,0],
    [0,1,0],
    [0,0,0]
    ]
    输出: 2
    解释:
    3x3 网格的正中间有一个障碍物。
    从左上角到右下角一共有 2 条不同的路径：
    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右

## 想法 ##

用上62题的题解，在循环中加上障碍物的判断就解决呢

## 结果 ##

超过93%的测试案例

时间复杂度/空间复杂度：n\*m/n

## 总结 ##

## 代码 ##

### 我的答案 ###

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
          return 0;
        }
    
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
    
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
              dp[i][j] = 0;
            } else {
              if (i == 0 && j == 0) {
                dp[i][j] = 1;
                continue;
              }
              if (i == 0) {
                dp[i][j] = dp[i][j - 1];
                continue;
              }
              if (j == 0) {
                dp[i][j] = dp[i - 1][j];
                continue;
              }
              dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
          }
        }
        return dp[m - 1][n - 1];
    
      }

### 大佬们的答案 ###

public int better(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] res = new int[n];
        res[0] = 1;
        for (int i = 0; i < m; i++) {
          for (int j = 0; j < n; j++) {
            if (obstacleGrid[i][j] == 1) {
              res[j] = 0;
            } else if (j > 0) {
              res[j] = res[j] + res[j - 1];
            }
          }
        }
        return res[n - 1];
      }

### 测试用例 ###

@Test
      public void test063() {
        // 创建测试案例
        int[][] arr1 = new int[3][3];
        arr1[0][0] = 0;
        arr1[0][1] = 0;
        arr1[0][2] = 0;
        arr1[1][0] = 0;
        arr1[1][1] = 1;
        arr1[1][2] = 0;
        arr1[2][0] = 0;
        arr1[2][1] = 0;
        arr1[2][2] = 0;
        int[][] arr2 = new int[1][1];
        arr2[0][0] = 1;
    
        // 测试案例期望值
        int expResult1 = 2;
        int expResult2 = 0;
    
        // 执行方法
        Solution063 solution063 = new Solution063();
        int result1 = solution063.uniquePathsWithObstacles(arr1);
        int result2 = solution063.uniquePathsWithObstacles(arr2);
    
        // 判断期望值与实际值
        Assert.assertEquals(expResult1, result1);
        Assert.assertEquals(expResult2, result2);
    
      }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan