剑指 Offer 13.机器人的运动范围

2022-09-13 | 2024-02-18 | 737 | 3 分钟

机器人的运动范围

dfs

解题思路：
- 可以理解为暴力法模拟机器人在矩阵中的所有路径；
- DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推；
- 剪枝：在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为可行性剪枝；
图解：
复杂度：
- 时间复杂度：O(MN)，最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)；
- 空间复杂度：O(MN)，最差情况下，二维数组存储矩阵所有单元格的索引，使用 O(MN) 的额外空间；

代码实现：

function movingCount(m: number, n: number, k: number): number {
    function dfs(i, j, m, n, k, visited) {
        // 基本判断 + 判断是否走过这条路
        if (i >= m || i < 0 || j >= n || j < 0 || visited[i][j]) {
            return;
        }

        // 没有走过，先标记，在判断是否符合题意
        visited[i][j] = true;

        // 求和
        let sum = i % 10 + j % 10 + Math.floor(i / 10) + Math.floor(j / 10);
        if (sum > k) return;

        // 符合题意数量+1
        res++;

        // 直接大范围撒网
        dfs(i + 1, j, m, n, k, visited);
        dfs(i, j + 1, m, n, k, visited);
    }

    let res = 0;
    // 用来做标记的数组
    let visited = new Array(m).fill(0).map(() => new Array(n));
    dfs(0, 0, m, n, k, visited);

    return res;
};

bfs+队列

解题思路：
- DFS 是沿着一个方向一直往下走，有一种不撞南墙不回头的感觉，直到不满足条件才会回头；
- 而 BFS 不是一条道走下去，会把离他最近的都访问一遍，访问完之后才开始访问第二近的……，一直这样下去，
- 所以最好的一种数据结构就是使用队列，因为队列是先进先出，离他最近的访问完之后加入到队列中，最先入队的也是最先出队的；
复杂度：
- 时间复杂度：O(MN)，最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)；
- 空间复杂度：O(MN)，最差情况下，二维数组存储矩阵所有单元格的索引，使用 O(MN) 的额外空间；

代码实现：

function movingCount(m: number, n: number, k: number): number {
    // visited 记录格子是否被访问过
    let visited = new Array(m).fill(0).map(() => new Array(n));
    let res = 0;
    // 创建一个队列，保存的是访问到的格子坐标，是个二维数组
    let queue = [[0, 0]];

    while (queue.length > 0) {
        let tmp = queue.shift();
        let i = tmp[0], j = tmp[1];

        // visited[i][j]判断这个格子是否被访问过
        if (i >= m || j >= n || visited[i][j]) continue;

        //标注这个格子被访问过
        visited[i][j] = true;

        // 求和
        let sum = i % 10 + j % 10 + Math.floor(i / 10) + Math.floor(j / 10);
        if (sum > k) continue;

        res++;

        // 把下格子加入到队列中
        queue.push([i + 1, j]);
        // 把右格子加入到队列中
        queue.push([i, j + 1]);
    }

    return res;
};

打赏作者

您的打赏是我前进的动力

微信

支付宝

第 4️⃣ 座大山：generator 生成器

第 4️⃣ 座大山：async、await 语法糖

中午好👏🏻，我是 ✍🏻 疯狂 codding 中...

粽子

这有关于产品、设计、开发的问题和看法，还有技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程

了解更多

1. 机器人的运动范围
2. dfs
3. bfs+队列