高频面试题 leetcode62/63-技术圈

作者|莱乌

前言

今天，小莱在leetcode上闲逛，突然眼前一亮，咦！这不是去年来百度二面时的一道算法题吗？没想到在这遇到了。想当时险些栽到上边，不过最后千钧一发之际，还是想到了解决方法，顺利拿到offer 。

画外音：后来，在小米的面试环节中也遇到了此题。

那么，今天小莱就给大家分享下这道动态规划题。

题目：

一个机器人位于一个 m × n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

说明：m 和 n 的值均不超过 100。

例如，上图是一个7 × 3 的网格。有多少可能的路径？

画外音：Leetcode第62题，中等/难度。

不同路径

我们由终点位置倒推，从图中可以看出，想要到达终点，A、B两点是必经之路。那么，我们想要得到起点到终点的路径数，计算出到达A、B两点的路径总数不就能够得出来了吗？但是A、B两点的路径数如何得出呢。

我们不妨再往前推，到达A点需要经过C或者D这两点，到达A点的路径数可以通过到达C、D两点的路径总数得知。

同样地，到达B点需要经过D点或E点，到达B点的路径数可以通过到达D、E两点的路径总数得知。

到这，聪明的你有没有发现规律：

每一个点可到达路径数 = 其相邻左边点可到达路径数 + 其相邻上边点可到达路径数

现在，我们可以回到起点了。

我们可以把m×n方格看作一个二维数组，数组中的每个元素表示：

起点到该方格的路径数

（默念三遍！！！）

如下图中，机器人到达第X行（仅第0行）或第Y列（仅第0列）中的任意方格都只有一条路径。因此，我们将第X行、第Y列的方格元素都置为1。

接着，我们继续向其它点走。现在分别经过路径一、路径二走到了S点，因此到达S点的路径有2条。

最终，我们得到这样一张网格，每个格子里记录了起点到该格的路径数。

但是如何用代码表示呢？上边提到，我们可以将其看作一个二维数组v[m][n]。初始时，将第0行、第0列赋值为1。通过双层循环，将目标点的上边元素与左边元素相加，即可得到当前路径数。

代码实现：

int uniquePaths(int m, int n){
    if (m == 1 || n == 1) {
        return 1;
    }

    int i, j;
    int v[m][n];

    for (i = 1; i < m; i++) {
        v[i][0] = 1;
        for (j = 1; j < n; j++) {
            v[0][j] = 1;
            v[i][j] = v[i][j-1] + v[i-1][j];
        }
    }

    return v[m-1][n-1];
}

画外音：本文使用C语言实现，但是不会涉及复杂的语言特性，所以无需担心看不懂。另外，代码实现小莱在leetcode亲测！！！

不同路径 II

进行到这里，我们就实现了机器人从起点到终点畅通无阻情况下所要走的路径。

你可能注意到了，小莱重点标记了下『畅通无阻』这4个字，这说明还有存在障碍物的情况。那么现在我们就来看看，存在障碍物的情况下，机器人所走的路径数有多少。

画外音：此题为Leetcode第63题，中等/难度。

如图中，给定一个二维数组obstacleGrid[m][n]，用1来表示障碍物，用0表示空位置。

同样地，我们还是用二维数组v[m][n]来表示机器人到达某个方格的路径数。

但是在处理时，与无障碍物不同的是，其不再是简单向右或向下移动。初始化和计算时要考虑障碍。

这里分为两种情况：

1、当障碍物出现在第0行或第0列，此时一旦遇到障碍，后续方格无法到达，因此后续行列路径数只能为0；

画外音：这里只给出第0行、第0列路径数。

2、当障碍物出现在非第0行与第0列的任意位置时，如果当前方格为障碍物时，可以直接将该方格赋值为0；

现在我们可以通过代码来实现了，首先初始化二维数组v[m][n]，值默认都为0。接着初始化第0行和第0列，当未遇到障碍物时路径数为1，否则为0，其后方格的路径也都为0。然后通过双层循环，将目标点的上边元素与左边元素相加，即可得到当前路径数（在这个过程中如果遇到障碍物的话其方格数为0）。

代码实现：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){
    // m代表行 n代表列
    int m = obstacleGridSize, n = * obstacleGridColSize;
    if (obstacleGrid[0][0] == 1) {
        return 0;
    }

    int i, j;
    int v[m][n];
    memset(v, 0, m * n * sizeof(int));
    //初始化第一列
    for (i = 0; i < m; i++) {
        if (obstacleGrid[i][0] == 1) {
            break;
        }
        v[i][0] = 1;
    }
    //初始化第一行
    for (j = 0; j < n; j++) {
        if (obstacleGrid[0][j] == 1) {
            break;
        }
        v[0][j] = 1;
    }

    for (i = 1; i < m; i++) {
        for (j = 1; j < n; j++) {
            v[i][j] = obstacleGrid[i][j] == 1 ? 0 : (v[i][j-1] + v[i-1][j]);
        }
    }

    return v[m-1][n-1];
}