LeetCode唯一路径问题得到错误答案 [英] LeetCode Unique Paths Problem Getting The Wrong Answer

问题描述

我正在一个名为leetcode的网站上遇到名为唯一路径的问题。问题是：给定具有1s和0s的2D矩阵，机器人将从左上角开始，并希望到达右下角。机器人只有2个动作：向右和向下。此外，还有障碍（以 1表示）。机器人无法越过障碍物。当我输入内容时，我的程序给我一个错误的答案：

  0000 
 0100 
 0000 
 0000 
  

应该输出7，因为从左上角的方块到右下角的正方形。我的程序输出2。我的猜测是，它只会一直向下，一直向右，一直一直向右，一直向下。但是，我不知道这种行为的原因，因为对我来说看起来不错。谁能告诉我为什么这样做呢？这是代码：

  class Solution {
 
 int [] [] check; 
 
 public int uniquePathsWithObstacles（int [] [] grid）{
 if（grid == null || grid.length == 0）
返回0; 
 
 check = new int [grid.length] [grid [0] .length]; 
 return uniquePaths（grid，0，0）; 
} 
 
 private int uniquePaths（int [] [] grid，int x，int y）{
 if（x> = grid [0] .length || y > = grid.length || grid [y] [x] == 1）
返回0; 
 
 else if（x == grid [0] .length-1&&y == grid.length-1）
返回1; 
 
 else if（check [y] [x]> 0）
 return check [y] [x]; 
 
 return grid [y] [x] = uniquePaths（grid，x + 1，y）+ uniquePaths（grid，x，y + 1）; 
} 
} 
  

解决方案

不需要递归的更好的实现，请从右下角开始。

如果这样做，您只需要记住一行（或一列），因此它既更快又需要更少的内存。

示例

让我们使用a像这样的网格。为了不混淆下面的路径计数数组，请使用符号代替数字来定义网格。

 。 。 。 。 。 
。 * *。 。 
。 。 。 。 。 
。 。 。 。 。 
  

现在为最后一行建立一个数组，其中有多少种方法可以从该行退出。 / p>

 。 。 。 。 。网格
的最后一行========= 
 1 1 1 1 1 path从每个像元到末尾的计数
  

对其上方的行重复此操作。 从右边计算，pathCount是向右走时的pathCount +向下走时的pathCount。

  。 。 。 。 。网格
的第三行1 1 1 1 1最后一行
的结果========= 
 5 4 3 2 1第三行
的结果 

由于完成后不再需要最后一行的值，因此我们可以重用数组并内联替换值。 / p>

再次重复。这次我们阻止了单元格，因此将这些单元格的pathCount设置为0。

 。 * *。 。网格
的第二行5 4 3 2 1第三行
的结果========= 
 5 0 0 3 1第二行
的结果 

最后：

 。 。 。 。 。网格
的第一行5 0 0 3 1第二行
的结果========= 
 9 4 4 4 1第一行
的结果 

最终结果：从左上角到右下角的9条唯一路径。

< hr>

使用网格的备用格式进行紧凑实现，以便于测试：

 静态int countPaths（String ... grid）{
 int [] path = new int [grid [0] .length（）+ 1]; 
 path [grid [0] .length（）-1] = 1; 
 for（int y = grid.length-1; y> = 0; y--）
 for（int x = grid [0] .length（）-1; x> = 0 ; x--）
 path [x] =（grid [y] .charAt（x）！='0'？0：path [x] + path [x + 1]））; 
返回路径[0]； 
} 
  

测试

  System.out.println（countPaths（ 00000，
 01100，
 00000，
 00000 ））; //打印：9 
  

  System.out.println（countPaths（ 000，
 000，
 000）））; //打印：6 
  

I'm doing this problem called "Unique Paths" on a site called leetcode. The problem is: given a 2D matrix with 1s and 0s, a robot starts at the top-left and wants to reach the bottom-right. The robot has only 2 moves: right and down. Also, there are obstacles (represented by a '1'). The robot cannot walk over the obstacles. My program is giving me a wrong answer when I give the input:

0000
0100
0000
0000

Which should output 7, because there are 7 paths from the top left square to the bottom right square. My program outputs 2. My guess is that it only goes all the way down and all the way right, and all the way right and all the way down. However, I don't know the cause of this behaviour, as it looks fine to me. Can anyone tell me why it's doing this? Here is the code:

class Solution {

    int[][] check;

    public int uniquePathsWithObstacles(int[][] grid) {
        if(grid == null || grid.length == 0)
            return 0;

        check = new int[grid.length][grid[0].length];
        return uniquePaths(grid, 0, 0);
    }

    private int uniquePaths(int[][] grid, int x, int y){
        if(x >= grid[0].length || y >= grid.length || grid[y][x] == 1)
            return 0;

        else if(x == grid[0].length - 1 && y == grid.length - 1)
            return 1;

        else if(check[y][x] > 0)
            return check[y][x];

        return grid[y][x] = uniquePaths(grid, x + 1, y) + uniquePaths(grid, x, y + 1);
    }
}

解决方案

For a "better" implementation that doesn't require recursion, start at the lower right.

If you do that, you only need to remember one row (or column), so it's both faster and requires less memory.

Example

Lets use a grid like this. To not confuse with the path-counting arrays below, using symbols instead of numbers to define the grid.

. . . . .
. * * . .
. . . . .
. . . . .

Now build an array for the last row, with how many ways to get the exit from there.

. . . . .   last row from grid
=========
1 1 1 1 1   pathCount from each cell to the end

Repeat that for the row above it. Calculate from the right, and pathCount is the pathCount when going right + pathCount when going down.

. . . . .   3rd row from grid
1 1 1 1 1   result from last row
=========
5 4 3 2 1   result for 3rd row

Since we won't need the last-row values any more when done, we can reuse the array and replace the values inline.

Repeat again. This time we have blocked cells, so setting pathCount of those cells to 0.

. * * . .   2nd row from grid
5 4 3 2 1   result from 3rd row
=========
5 0 0 3 1   result for 2nd row

And finally:

. . . . .   1st row from grid
5 0 0 3 1   result from 2nd row
=========
9 4 4 4 1   result for 1st row

Final result: 9 unique paths from upper-left to lower-right.

---

Compact implementation using alternate format for the grid for easier testing:

static int countPaths(String... grid) {
    int[] paths = new int[grid[0].length() + 1];
    paths[grid[0].length() - 1] = 1;
    for (int y = grid.length - 1; y >= 0; y--)
        for (int x = grid[0].length() - 1; x >= 0; x--)
            paths[x] = (grid[y].charAt(x) != '0' ? 0 : paths[x] + paths[x + 1]);
    return paths[0];
}

Tests

System.out.println(countPaths("00000",
                              "01100",
                              "00000",
                              "00000")); // prints: 9

System.out.println(countPaths("000",
                              "000",
                              "000")); // prints: 6

这篇关于LeetCode唯一路径问题得到错误答案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！