63 Unique Paths 2【again】

A robot is located at the top-left corner of a_m_x_n_grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be?

Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

my version [3 points]

有两个edge case没考虑好

一是如果起点就是wall 比如【【1， 0】】 expect 0

二是在处理横竖两条边界的时候，没考虑前面为1 的情况

time & space O(m * n)

Input:
[
  [0,0],
  [1,1],
  [0,0]
]
Output: 0

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        if (obstacleGrid[0][0] == 1) {
            return 0;
        } 
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        int[][] res = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            if(i > 0 && (obstacleGrid[i-1][0] == 1 || res[i-1][0] == -1)) {
                res[i][0] = -1;
            }
            else if (obstacleGrid[i][0] == 1) {
                res[i][0] = -1;
            }else{
                res[i][0] = 1;
            }
        }
        for (int i = 0; i < cols; i++) {
            if (i > 0 && (obstacleGrid[0][i-1] == 1 || res[0][i-1] == -1)){
                 res[0][i] = -1;
            }
            else if (obstacleGrid[0][i] == 1 ) {
                res[0][i] = -1;
            }else{
                res[0][i] = 1;
            }
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (obstacleGrid[i][j] == 1) {
                    res[i][j] = -1;
                    continue;
                }
                if (res[i-1][j] != -1) {
                    res[i][j] += res[i-1][j];
                }
                if (res[i][j-1] != -1) {
                    res[i][j] += res[i][j-1];
                }
            }
        }
        if (res[rows-1][cols-1] == -1 ) {
            return 0;
        }
        return res[rows - 1][cols - 1];
    }
}

面试中如果考的话，肯定是希望降维度为1

if (obstacleGrid[i][j] == 1) {
                    res[j] = 0;

                }else if (j > 0){
                    res[j] += res[j-1];
                }

这一段的逻辑，降为0已经是最大的惩罚了

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null || obstacleGrid.length == 0|| obstacleGrid[0].length ==0) {
            return 0;
        }
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        int[] res = new int[cols];
        res[0] = 1;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (obstacleGrid[i][j] == 1) {
                    res[j] = 0;

                }else if (j > 0){
                    res[j] += res[j-1];
                }
            }
        }
        return res[cols - 1];
    }
}

05/23

Bloomberg phone interview

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
            return 0;
        }
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int rows = obstacleGrid.length;
        int cols = obstacleGrid[0].length;
        if (obstacleGrid[rows - 1][cols - 1] == 1) {
            return 0;
        }
        int[] res = new int[cols];
        res[0] = 1;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (obstacleGrid[i][j] == 1) {
                    res[j] = 0;
                }else {
                    if (j > 0) {
                        res[j] = res[j] + res[j - 1];
                    }
                }
            }
        }
        return res[cols - 1];
    }
}