Leetcode - Unique Paths II

Paste_Image.png

My code:

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
            return 0;
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;   
        if (obstacleGrid[row - 1][col - 1] == 1)
            return 0;
        else if (row == 1) {
            for (int i = 0; i < col; i++)
                if (obstacleGrid[0][i] == 1)
                    return 0;
            return 1;
        }
        else if (col == 1) {
            for (int i = 0; i < row; i++)
                if (obstacleGrid[i][0] == 1)
                    return 0;
            return 1;
        }
        /* initialization for the last row */
        int indexCol = col - 2;
        while (indexCol >= 0 && obstacleGrid[row - 1][indexCol] != 1)
            obstacleGrid[row - 1][indexCol--] = 1;
        while(indexCol >= 0)
            obstacleGrid[row - 1][indexCol--] = 0;
        
        /* initialization for the last col */
        int indexRow = row - 2; 
        while (indexRow >= 0 && obstacleGrid[indexRow][col - 1] != 1)
            obstacleGrid[indexRow--][col - 1] = 1;
        while (indexRow >= 0)
            obstacleGrid[indexRow--][col - 1] = 0;
        
        /* initialize the [][] array which records the result */
        for (int i = row - 2; i >= 0; i--)
            for (int j = col - 2; j >= 0; j--)
                if (obstacleGrid[i][j] == 1)
                    obstacleGrid[i][j] = 0;
                else
                    obstacleGrid[i][j] = obstacleGrid[i + 1][j] + obstacleGrid[i][j + 1];
        
        return obstacleGrid[0][0];
    }
    
    public static void main(String[] args) {
        Solution test = new Solution();
        int[][] a = new int[2][2];
        System.out.println(test.uniquePathsWithObstacles(a));
    }
}

My test result:

Paste_Image.png

这道题目不难。同样的初始化最后一行和最后一列。但是从右往左遍历，碰到0就置为1.然后碰到1之后，后面的所有都全部置为0.
然后遍历数组。如果碰到1就置为0.如果碰到0，就变成右侧和下侧之和。
然后就出来了。

**
总结： Array
**

Anyway, Good luck, Richardo!

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0)
            return 0;
        int i = 0;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1)
            return 0;
        /** initialize with first row */
        for (; i < n; i++) {
            if (obstacleGrid[0][i] == 0)
                obstacleGrid[0][i] = 1;
            else
                break;
        }
        for (; i < n; i++)
            obstacleGrid[0][i] = 0;
        /** initialize with first col */
        i = 0;
        obstacleGrid[0][0] = 0;
        for (; i < m; i++) {
            if (obstacleGrid[i][0] == 0)
                obstacleGrid[i][0] = 1;
            else
                break;
        }
        for (; i < m; i++)
            obstacleGrid[i][0] = 0;
        
        obstacleGrid[0][0] = 1;
        for (i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)
                    obstacleGrid[i][j] = 0;
                else
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
            }
        }
        return obstacleGrid[m - 1][n - 1];
    }
}

感觉和之前相比思路更加清晰了。
写代码的时候尽量不要涉及到
布尔值，if语句中的多个布尔值判断，
明码的操作，如 col - 2，这样的。
一旦代码变长了而你又好久不看了，这代码就成垃圾了。
尽量用数据结构去代替布尔值和布尔判断

Anyway, Good luck, Richardo!

状态不好，提交了好多次才成功。上面的做法不错。

Anyway, Good luck, Richardo! -- 08/08/2016