首页 > 代码库 > 【LeetCode-面试算法经典-Java实现】【063-Unique Paths II(唯一路径问题II)】

【LeetCode-面试算法经典-Java实现】【063-Unique Paths II(唯一路径问题II)】

【063-Unique Paths II(唯一路径问题II)】


【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】

原题

  Follow up for “Unique Paths”:
  Now consider if some obstacles are added to the grids. How many unique paths would there be?


  An obstacle and empty space is marked as 1 and 0 respectively in the grid.
  For example,
  There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

  The total number of unique paths is 2.
  Note: m and n will be at most 100.

题目大意

  唯一路径问题兴许。假设路径中有障碍,求总的路径的种数。

【唯一路径问题】
  注意:网格的行数和列数都不超过100

解题思路

  採用分治求解方法
  用一个m*n的组数A保存结果。
  对于A数组中的元素有。
  1、当x=0或者y=0时。而且(x, y)位置无障碍。

有A[x][y] = 1。 有障碍就是0
  2、当x>=1而且y>=1时,而且(x, y)位置无障碍。

有A[x][y] = A[x-1][y]+A[x][y-1]。 有障碍就是0
  3、所求的结点就是A[m-1][n-1]。

代码实现

算法实现类

public class Solution {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 输入校验
        if (obstacleGrid == null || obstacleGrid.length < 1 || obstacleGrid[0].length < 1
                || obstacleGrid[0][0] == 1
                || obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
            return 0;
        }

        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        int[][] result = new int[rows][cols];

        // 第一个位置有多少种方法。无障碍就是1种,有障碍就是0种
        result[0][0] = obstacleGrid[0][0] == 0 ?

1 : 0; for (int i = 1; i < cols; i++) { result[0][i] = obstacleGrid[0][i] == 0 ? result[0][i - 1] : 0; } for (int i = 1; i < rows; i++) { result[i][0] = obstacleGrid[i][0] == 0 ? result[i - 1][0] : 0; } for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { result[i][j] = obstacleGrid[i][j] == 0 ?

result[i - 1][j] + result[i][j - 1] : 0; } } return result[rows - 1][cols - 1]; } // 使用递归方法会超时 public int uniquePathsWithObstacles2(int[][] obstacleGrid) { // 输入校验 if (obstacleGrid == null || obstacleGrid.length < 1 || obstacleGrid[0].length < 1 || obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) { return 0; } int[] result = {0}; solve(obstacleGrid, 0, 0, result); return result[0]; } public void solve(int[][] grid, int row, int col, int[] sum) { // 到达终点 if (row == grid.length - 1 && col == grid[0].length - 1) { sum[0]++; } // 没有到终点,点在棋盘内。而且当前位置不是 else if (row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] == 0) { // 往右走 solve(grid, row, col + 1, sum); // 往下走 solve(grid, row + 1, col, sum); } } }

评測结果

  点击图片,鼠标不释放,拖动一段位置,释放后在新的窗体中查看完整图片。

技术分享

特别说明

欢迎转载,转载请注明出处【http://blog.csdn.net/derrantcm/article/details/47182723】

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

【LeetCode-面试算法经典-Java实现】【063-Unique Paths II(唯一路径问题II)】