首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer 13——机器人的运动范围

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

作者头像
健程之道
发布2020-05-17 20:00:57
3630
发布2020-05-17 20:00:57
举报
文章被收录于专栏:健程之道健程之道

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

原题

地上有一个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)

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

总结

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

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-05-08,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 健程之道 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 原题
  • 解题
    • 深度优先搜索
      • 广度优先搜索
        • 求坐标之和
        • 总结
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档