专栏首页健程之道剑指offer 13——机器人的运动范围

剑指offer 13——机器人的运动范围

这道题本质还是搜索,因此可以使用深度优先搜索和广度优先搜索进行解决。

原题

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 35, 37 ,因为3+5+3+7=18。但它不能进入方格 35, 38,因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3
示例 2:

输入:m = 3, n = 1, k = 0
输出:1

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

原题url:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

解题

深度优先搜索

从一个点出发,遍历完所有点,为了保证不会重复遍历,因此我们可以借助一个二维矩阵记录已经遍历过的点。而用深度优先搜索遍历的话,一般都是使用递归的。

需要注意的是,虽然机器人可以上下左右移动,但因为是从[0, 0]开始的,所以可以想象成根节点往子节点或兄弟节点的遍历方式,深度优先搜索就是先遍历子节点,子节点遍历完成后,在遍历兄弟节点。

终止条件应该有:

  1. 坐标越界,也就是 x >= m 或者 y >= n
  2. 该点已经访问过,既然访问过,自然不用重新计算。
  3. 坐标数字之和大于 k

求数字各数位之和,最简单的方法应该就是 摸除% + 整除/ 就可以了。

我们来看看代码:

class Solution {
    public int movingCount(int m, int n, int k) {
        int result = 0;
        int max = m > n ? m : n;
        // key为数字,value为该数字各位之和
        Map<Integer, Integer> numMap = new HashMap<>(max * 4 / 3 + 1);
        // 记录已经访问过的节点
        boolean[][] visited = new boolean[m][n];
        // 从(0, 0)开始移动
        return move(0, 0, m, n, k, numMap, visited);
    }

    public int move(int x, int y, int m, int n, int k, Map<Integer, Integer> numMap, boolean[][] visited) {
        // 是否越界
        if (x >= m || y >= n) {
            return 0;
        }

        // 如果该节点已经访问过
        if (visited[x][y] == true) {
            // 说明该方格所代表的次数已经被计算过,因此返回0
            return 0;
        }

        // 标记该节点已经访问过
        visited[x][y] = true;
        // 计算
        int xSum = getNumSum(x, numMap);
        int ySum = getNumSum(y, numMap);
        if (xSum + ySum > k) {
            return 0;
        }

        // 尝试向下、向右
        return 1 + move(x + 1, y, m, n, k, numMap, visited) + move(x, y + 1, m, n, k, numMap, visited);
    }

    public int getNumSum(int num, Map<Integer, Integer> numMap) {
        Integer sum = numMap.get(num);
        if (sum != null) {
            return sum;
        }

        int key = num;
        sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        numMap.put(key, sum);
        return sum;
    }
}

提交OK。我们来看看这种方法的复杂度:

  • 时间复杂度 O(MN) :最差情况下,机器人遍历矩阵所有单元格,此时时间复杂度为 O(MN)。
  • 空间复杂度 O(MN) :visited 矩阵的大小就是 mn,因此使用了 O(MN) 的额外空间。

广度优先搜索

广度优先搜索,也就是从根节点出发,先遍历兄弟节点,再遍历子节点。一般我们都需要借助一个队列存储已经即将要遍历的节点,因为队列的特性是先进先出,因此当父节点遍历完成后,会依序遍历所有该父节点的所有子节点(这些节点都是兄弟),再遍历下一层的子节点。

(PS:现在想想,如果用栈存储已经遍历过的节点,也是可以的,只是访问节点的方式并没有什么规律可言。)

针对该机器人的运动,也是从 [0, 0] 出发,向下向右移动,层层递进。

接下来我们看看代码:

class Solution {
    public int movingCount(int m, int n, int k) {
        int result = 0;
        int max = m > n ? m : n;
        // key为数字,value为该数字各位之和
        Map<Integer, Integer> numMap = new HashMap<>(max * 4 / 3 + 1);
        // 记录已经访问过的节点
        boolean[][] visited = new boolean[m][n];
        // 记录还未访问结束的点
        Queue<Coordinate> queue = new LinkedList<>();
        // 从(0, 0)开始移动
        queue.offer(new Coordinate(0, 0));
        while (!queue.isEmpty()) {
            // 获取队首元素
            Coordinate coordinate = queue.poll();
            // 判断当前坐标是否有效
            if (coordinate.x >= m || coordinate.y >= n) {
                continue;
            }
            // 判断当前左边是否已经访问过
            if (visited[coordinate.x][coordinate.y]) {
                continue;
            }
            // 标记当前坐标已经访问过
            visited[coordinate.x][coordinate.y] = true;
            // 判断当前坐标是否有效
            int xSum = getNumSum(coordinate.x, numMap);
            int ySum = getNumSum(coordinate.y, numMap);
            if (xSum + ySum > k) {
                continue;
            }
            // 如果有效
            result++;
            // 将下边一格节点放入队列中
            queue.add(new Coordinate(coordinate.x + 1, coordinate.y));
            // 将右边一格节点放入队列中
            queue.add(new Coordinate(coordinate.x, coordinate.y + 1));
        }
        return result;
    }

    public int getNumSum(int num, Map<Integer, Integer> numMap) {
        Integer sum = numMap.get(num);
        if (sum != null) {
            return sum;
        }

        int key = num;
        sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        numMap.put(key, sum);
        return sum;
    }

    class Coordinate {
        int x;
        int y;

        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

提交OK。我们来看看这种方法的复杂度:

  • 时间复杂度 O(MN) :最差情况下,机器人遍历矩阵所有单元格,此时时间复杂度为 O(MN)。
  • 空间复杂度 O(MN) :visited 矩阵的大小就是 mn,因此使用了 O(MN) 的额外空间。

既然上下两种方法时间复杂度相同,但比较奇怪的在于,我在力扣上提交时,上面一种方法所花费的时间是 1ms ,但这种方法所花费的时间是 7ms 。既然复杂度的计算是忽略了系数、低阶、常数,但我认为上下两种方法即使不忽略,应该也是一样的。 如果你有新的看法,欢迎指教。

求坐标之和

求坐标之和的方法,我写的是比较简单的一种,但如果你好好想想,就可以发现有更简单的方法。

正常情况下,随着数字逐渐变大,数字各位之和应该也是逐渐上升的,但唯一的特殊情况就是 进位 ,比如 19 变到 20 ,各数位之和从 10 变为 2,其实细心点就可以发现,十位数虽然加1,但个位数减9,因此总体减8。所以可以总结出:

假设现在的数字为x,其各位数之和为Sum(x),那么下一个Sum(x + 1)为:
Sum(x + 1) = ((x + 1) % 10 == 0) ? (Sum(x) - 8) : (Sum(x) + 1)

那么上面的代码还有可以优化的地方,这个就留给大家去完成了。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题本质还是搜索,因此可以使用深度优先搜索和广度优先搜索进行解决。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健壮

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动,每一次只能向左右上下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大...

    瑞新
  • 剑指Offer - 面试题13. 机器人的运动范围(BFS/DFS)

    地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(...

    Michael阿明
  • 剑指offer 机器人的运动范围

    版权声明:本文为博主-姜兴琪原创文章,未经博主允许不得转载。 https://blog.cs...

    week
  • 剑指offer——机器人的运动范围

    题目描述 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和...

    AI那点小事
  • 剑指offer - 机器人的运动范围 - JavaScript

    题目描述:地上有一个 m 行 n 列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右...

    心谭博客
  • 剑指offer第11题:机器人运动范围

    此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

    鹏-程-万-里
  • 每天一道剑指offer-机器人的运动范围

    地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。...

    乔戈里
  • 每日一题 剑指offer(机器人的运动范围)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • 剑指offer_25_机器人的运动范围

    解析:采用回溯法,定义一个数组来记录机器人所到过的位置,防止重复计算,然后分别向四个方向移动,判断是否能到达。

    用户6055494

扫码关注云+社区

领取腾讯云代金券