因为它,差点无缘大厂梦!!!

时间:2024-01-27 14:53:35

前言

今天,小莱在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];
}