解题思路：用二维数组存储达到每一步可能的路径数，上一步对下一步有记忆效应（动态规划的思想），除第一行和第一列，其他格数的路径数是由上边和左边的路径数决定的。
难点：想到用动态规划就可以，另外熟练二维数组的使用(c语言动态申请二维数组)
java代码：
public class leecode63 {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0 || obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
// 遍历首行，该位置值为1则证明有障碍，不可通过，设置该位置值为0；若为0，设置为上一个的值(设置第一个元素为1)
for (int i = 1; i < obstacleGrid[0].length; i++) {
obstacleGrid[0][i] = (obstacleGrid[0][i] == 0) ? obstacleGrid[0][i - 1] : 0;
}
// 遍历首列，该位置有1，设置为0；如果为0，设置为上一个的值
for (int j = 1; j < obstacleGrid.length; j++) {
obstacleGrid[j][0] = (obstacleGrid[j][0] == 0) ? obstacleGrid[j - 1][0] : 0;
}
// 遍历剩下的元素，如果值为1，证明有障碍，设置为0；如果时0，设置为上和左值的和
for (int i = 1; i < obstacleGrid.length; i++) {
for (int j = 1; j < obstacleGrid[0].length; j++) {
obstacleGrid[i][j] = (obstacleGrid[i][j] == 1) ? 0 : (obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]);
}
}
return obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
}
}
测试用例：
package leetcode;
import org.junit.Test;
import static org.junit.Assert.*;
public class leecode63Test {
@Test
public void uniquePathsWithObstacles() {
assertTrue(new leecode63().uniquePathsWithObstacles(new int[][]{{0,0,0},{0,1,0},{0,0,0}}) == 2);
}
@Test
public void uniquePathsWithObstacles1() {
assertTrue(new leecode63().uniquePathsWithObstacles(null) == 0);
}
@Test
public void uniquePathsWithObstacles2() {
assertTrue(new leecode63().uniquePathsWithObstacles(new int[][]{{1}}) == 0);
}
@Test
public void uniquePathsWithObstacles3() {
assertTrue(new leecode63().uniquePathsWithObstacles(new int[][]{{0, 0}, {0, 1}}) == 0);
}
@Test
public void uniquePathsWithObstacles4() {
assertTrue(new leecode63().uniquePathsWithObstacles(new int[][]{{}}) == 0);
}
}
c代码：
int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize)
{
// 二维指针数组
// int (*ob) [*obstacleGridColSize] = obstacleGrid;
// 异常输入
if (obstacleGrid == NULL
|| obstacleGrid == NULL
|| obstacleGridSize < 1
|| *obstacleGridColSize < 1
|| obstacleGrid[0][0] == 1) {
return 0;
}
obstacleGrid[0][0] = 1;
// 遍历首行，该位置值为1则证明有障碍，不可通过，设置该位置值为0；若为0，设置为上一个的值(设置第一个元素为1)
for (int i = 1; i < obstacleGridSize; i++) {
if (obstacleGrid[0][i] == 1) {
obstacleGrid[0][i] = 0;
} else {
obstacleGrid[0][i] = obstacleGrid[0][i-1];
}
}
// 遍历首列，该位置有1，设置为0；如果为0，设置为上一个的值
for (int i = 1; i < *obstacleGridColSize; i++) {
if (obstacleGrid[i][0] == 1) {
obstacleGrid[i][0] = 0;
} else {
obstacleGrid[i][0] = obstacleGrid[i-1][0];
}
}
// 遍历剩下的元素，如果值为1，证明有障碍，设置为0；如果时0，设置为上和左值的和
for (int i = 1; i < obstacleGridSize; i++) {
for (int j = 1; j < *obstacleGridColSize; j++) {
if (obstacleGrid[i][j] == 1) {
obstacleGrid[i][j] = 0;
} else {
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1];
}
}
}
return obstacleGrid[obstacleGridSize-1][*obstacleGridColSize-1];
}
测试用例：
int a[3][3] = {
{0, 0, 0},
{0, 1, 0},
{0, 0, 0}
};
int *q[3] = {&a[0][0], &a[1][0], &a[2][0]};
printf("result is %d\n", uniquePathsWithObstacles(q, 3, &b));
附录：
C标准库里的实用函数：-
快排：qsort
用法：先定义个比较函数，然后作为函数指针传给快排函数的第四个参数
int compare(const void *a, const void*b) {
return *(int *)a - *(int *)b;
}
qsort(allNum, len, sizeof(int), compare);
- 二分查找：bsearch
用法：依然是先定义个比较函数，如果找到了返回该元素的指针，否则返回空指针；
参数的含义依次是：要查找的元素的指针，数组指针，数组大小，数组元素大小， 比较函数指针
item = (int*) bsearch (&key, values, 5, sizeof (int), cmpfunc);
- 数据结构与算法的可视化动画学习网站：
