Unique Paths II, Leetcode 解题笔记

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 3×3 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.

Unique Paths的基础上稍作改动,每次更新数组中的元素时先判断当前是否是障碍物,如果是,则当前的path数变成0。同样这道题考察的难点主要是二维数组的边界情况处理,一些特殊的case一定要考虑到。

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] store = new int[n];
        boolean flag = true;
        
        //initialize the first row
        for(int i = 0; i < n; i++){
            if(obstacleGrid[0][i] == 1){
                flag = false;
            }
            if(flag){
                store[i] = 1;
            }
            else{
                store[i] = 0;
            }
        }
        
        for(int i = 1; i < m; i++){
            //handle the first element of each row
            if(obstacleGrid[i][0] == 1){
                store[0] = 0;
            }
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1){
                    store[j] = 0;
                }
                else{
                    store[j] = store[j] + store[j-1];
                }
            }
        }
        return store[n-1];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s