leetCode解题: 63. 不同路径 II

解题思路：用二维数组存储达到每一步可能的路径数，上一步对下一步有记忆效应（动态规划的思想），除第一行和第一列，其他格数的路径数是由上边和左边的路径数决定的。

难点：想到用动态规划就可以，另外熟练二维数组的使用(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);

• 数据结构与算法的可视化动画学习网站：

1. https://algorithm-visualizer.org
2. https://visualgo.net/en