leetCode解题报告5道题(十一)

ways[row][col] = ways[row+1][col] + ways[row][col+1]  (0<= row <=m-2, 0<= col <=n-2)

通过这样的分析，我们再来看看代码，理解下哈！

AC代码：

public class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0)
            return 0;
        if (m == 1){
            return 1;
        }
        if (n == 1){
            return 1;
        }
        int[][] ways = new int[m][n];
        //最后一列所有的位置的走法都只有1种
        for (int i=0; i            ways[i][n-1] = 1;
        }
        //最后一行所有的位置的走法都只有1种
        for (int j=0; j            ways[m-1][j] = 1;
        }
        //update
        for (int row=m-2; row>=0; --row){
            for (int col=n-2; col>=0; --col){
                ways[row][col] = ways[row+1][col] + ways[row][col+1];
            }
        }
        return ways[0][0];
    }
}

题目四：Unique Paths II

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.

分析：

这道题目跟上面的非常像，只是在判断的时候需要先判断当前自身这个位置是否是1，如果是1表示当前位置是障碍，这样子到达终点的不同路径数就为0，如果不是障碍物的话，那么判断它的右边元素是否是1，不是1的话，加上右边元素对应的路径数，然后再判断它的下面元素是否是1，不是1的话，加上下边元素对应的路径数。

还有要注意的是当开始start元素(0,0)就为1（障碍物）的话 或者 end元素(m-1, n-1)为1(障碍物)那么这样直接返回0，表示没有路径数可以到达终点。 

最终ways[0][0]即是我们所要求解的最后结果。

AC代码：

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m == 0)
            return 0;
        int n = obstacleGrid[0].length;
        if (n == 0)
            return 0;
        if (m == 1 || n == 1){
            return (obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1) ? 0 : 1;
        }
        //终点或者起点为1，表示为障碍物，直接返回0
        if (obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1){
            return 0;
        }
        //存储路径数
        int[][] ways = new int[m][n];
        //处理最后一列
        for (int i=m-2; i>=0; --i){
            if(obstacleGrid[i+1][n-1] != 1 && obstacleGrid[i][n-1] != 1){
                ways[i][n-1] = 1;
            }else{
                ways[i][n-1] = 0;
                obstacleGrid[i][n-1] = 1;
            }
        }
        //处理最后一行
        for (int j=n-2; j>=0; --j){
            if(obstacleGrid[m-1][j+1] != 1 && obstacleGrid[m-1][j] != 1){
                ways[m-1][j] = 1;
            }else{
                ways[m-1][j] = 0;
                obstacleGrid[m-1][j] = 1;
            }
        }
        //update
        for (int row=m-2; row>=0; --row){
            for (int col=n-2; col>=0; --col){
                if (obstacleGrid[row][col] == 1){
                    continue;
                }
                ways[row][col] = 0;
                if (obstacleGrid[row+1][col] != 1){
                    ways[row][col] += ways[row+1][col];
                }
                if (obstacleGrid[row][col+1] != 1){
                    ways[row][col] += ways[row][col+1];
                }
                if (ways[row][col] == 0){
                    obstacleGrid[row][col] = 1;
                }
            }
        }
        return ways[0][0];
    }
}

题目五：

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

分析：

找到最长的那块木板，假设其下标为maxValueIndex。

分别从左侧和右侧向最长的木板靠近。

左侧逼近过程：（i  :  0 ~~ maxValueIndex）

用一个max来记录现在已经遍历到的木板中最长的那个的长度。

1、如果一个木板的长度A[i] maxValueIndex 并且 A[i] ，所以这块木板的左右两侧各有一个木板长于它。则在这块木板上能存的水量为：max - 该木板的长度。

2、如果一个木板的长度A[i]  >max，max对应的位置<该木板的位置 < maxValueIndex 并且A[i]  >max, 所以在该木板左右两侧只有一个木板（maxIdx）长于它。则这块木板上不能存水，则更新max值等于A[i]。

右侧逼近过程与左侧相似：（i  :  len - 1 ~~ maxValueIndex）

AC代码：

public class Solution {
    public int trap(int[] A) {

        int len = A.length;
        if (len == 0 || len == 1){
            return 0;
        }
        int sum = 0;
        //找最大的木板的下标哈
        int maxValueIndex = 0;
        int max = 0;
        for (int i=0; i            if (max                 max = A[i];
                maxValueIndex = i;
            }
        }
        //从左向最大值逼近
        max = A[0];
        for (int i=1; i            if (A[i] > max){
                max = A[i];
            }else{
                sum += (max - A[i]);
            }
        }
        //从右向最大值逼近
        max = A[len-1];
        for (int i=len-2; i>maxValueIndex; --i){
            if (A[i] > max){
                max = A[i];
            }else{
                sum += (max - A[i]);
            }
        }
        
        return sum;
    }
}