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
