LeetCode(87) -- 63, 74,

P63. Unique Paths II (Medium)

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?

My Solution

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null) {
            return 0;
        }
        if (obstacleGrid.length == 0) {
            return 0;
        }
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        obstacleGrid[0][0] = 1;
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        
        // 第一行
        for (int i = 1; i < col; i++) {
            if (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) {
                obstacleGrid[0][i] = 1;
            } else {
                obstacleGrid[0][i] = 0;
            }
        }
        
        // 第一列
        for (int i = 1; i < row; i++) {
            if (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) {
                obstacleGrid[i][0] = 1;
            } else {
                obstacleGrid[i][0] = 0;
            }
        }
        
        // 从obstacleGrid[1][1]开始遍历到右下角
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    obstacleGrid[i][j] = 0;
                } else {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                }
            }
        }
        
        return obstacleGrid[row - 1][col - 1];
    }
}

100%

The Best Solution

class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        if(grid[0][0] ==1)return 0;
        
        int R = grid.length;
        int C = grid[0].length;

        // If the starting cell has an obstacle, then simply return as there would be
        // no paths to the destination.
        if (grid[0][0] == 1) {
            return 0;
        }

        // Number of ways of reaching the starting cell = 1.
        grid[0][0] = 1;

        // Filling the values for the first column
        for (int i = 1; i < R; i++) {
            grid[i][0] = (grid[i][0] == 0 && grid[i - 1][0] == 1) ? 1 : 0;
        }

        // Filling the values for the first row
        for (int i = 1; i < C; i++) {
            grid[0][i] = (grid[0][i] == 0 && grid[0][i - 1] == 1) ? 1 : 0;
        }
        
        for(int i = 1; i < grid.length; i++){
            for(int j = 1; j < grid[0].length; j++){
                 if (grid[i][j] == 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
                } else {
                    grid[i][j] = 0;
                }
                
            }
        }
        
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

P74. Search a 2D Matrix (Medium)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

My Solution

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int midElement = matrix[mid / n][mid % n];
            if (target == midElement) {
                return true;
            } else if (target < midElement) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
}

100%

P75. Sort Colors (Medium)

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Solution

class Solution {
    public void sortColors(int[] nums) {
        int l = 0, r = nums.length - 1;
        int current = 0;
        while (current <= r) {
            if (nums[current] == 2) {
                int temp = nums[current];
                nums[current] = nums[r];
                nums[r] = temp;
                r--;
            } else if (nums[current] == 0) {
                int temp = nums[current];
                nums[current++] = nums[l];
                nums[l] = temp;
                l++;
            } else {
                current++;
            }
        }
    }
}

100%