梦里一明月
2021-07-18 11:16
采纳率: 100%
浏览 35
已采纳

leetcode63:算法相同 代码也很相似 为何运行结果不一致?

原题连接:leetcode63:不同路径II
先贴出题解的正确通过的代码:

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m&&obstacleGrid[i][0] == 0; i++) {
                dp[i][0] = 1;
        }
        for (int j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
                dp[0][j] = 1;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

第二个是我自己写的,只有一个地方不同,那就是前两个循环中题解是在for循环语句这一行中做了判断,而我是另外用if语句做了判断

两个代码的运行结果却不一致,没搞明白是为什么?

public int uniquePathsWithObstacles(int[][] obstacleGrid){
        if (obstacleGrid == null || obstacleGrid.length == 0) {
            return 0;
        }
        int m=obstacleGrid.length,n=obstacleGrid[0].length;
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            if(obstacleGrid[i][0]==0)
                dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if(obstacleGrid[0][i]==0)
                dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if(obstacleGrid[i][j]==0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m- 1][n - 1];
    }

结果不一致的输入样例如下:
{{0,0},{1,1},{0,0}}

正确答案是0,而第二个代码运行结果为1 ,没想明白是什么原因

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • CSDN专家-sinjack 2021-07-18 11:23
    已采纳

    那肯定不一样的啊。
    第一种写法的循环终止条件是两个,你写的循环终止条件是一个。好好理解一下。
    对于第一种写法:如果循环终止条件是判断不满足就不会执行。
    对于第二种写法:会依然执行,因为第一个循环判断成立,只是内部的if条件不成立。

    点赞 评论
  • 这个循环不一样,取到的值不同了。
    for (int j = 0; j < n&&obstacleGrid[0][j] == 0; j++) {
    dp[0][j] = 1;
    }

    点赞 评论
  • 404警告 2021-07-18 13:27

    主要看循环条件:正确代码

    
    // 二维数组{{10}} j定义为0 n的长度为2 必须满足条件是j<2 也就是0<2 为true 
    // 且obstacleGrid[0][j] == 0 也就是obstacleGrid[0][0] == 0 条件不满足 为false 是不会进入for循环 在入口就给终止
      for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
         dp[0][j] = 1;
      }
    

    错误代码:

    // 二维数组{{10}} i定义为0 n的长度为2 必须满足条件是i<2 也就是0<2 为true
    // 进入循环 第一次obstacleGrid[0][i] == 0条件为false 因为这个下标的值是1 进入第二次循环 i=1的时候 obstacleGrid[0][i] == 0条件为true
    // 改变dp[0][i] == 1的值 这个循环是会进入且循环完毕 找到满足条件的就进行改值
       for (int i = 0; i < n; i++) {
           if (obstacleGrid[0][i] == 0)
             dp[0][i] = 1;
           }
    
    

    两者之间区别在于 第一个循环会在条件位置给你终止循环 让你进不去 第二次循环是进去了 每次循环都在找符合条件的机会进行改值

    点赞 评论

相关推荐 更多相似问题