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

栏目: IT技术 · 发布时间: 4年前

内容简介:这道题本质还是搜索,因此可以使用深度优先搜索和广度优先搜索进行解决。<!-- more -->地上有一个m行n列的方格,从坐标

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

<!-- more -->

原题

地上有一个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/probl...

解题

深度优先搜索

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

需要注意的是,虽然机器人可以上下左右移动,但因为是从 [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)

广度优先搜索

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

(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)

既然上下两种方法时间复杂度相同,但比较奇怪的在于,我在力扣上提交时,上面一种方法所花费的时间是 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)

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

总结

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

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

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

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


以上所述就是小编给大家介绍的《剑指offer 13——机器人的运动范围》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

疯传

疯传

乔纳·伯杰 (Jonah Berger) / 刘生敏、廖建桥 / 电子工业出版社 / 2014-1-1 / CNY 48.00

《疯传:让你的产品、思想、行为像病毒一样入侵》内容简介:是什么让事物变得流行?从买轿车、买衣服、吃三明治,到给孩子取名字,你是否知道为什么某些产品会大卖,某些故事被人们口口相传,某些电子邮件更易被转发,或者某些视频链接被疯狂地点击,某些谣言更具传播力,某些思想和行为像病毒一样入侵你的大脑……《疯传:让你的产品、思想、行为像病毒一样入侵》这本书将为你揭示这些口口相传和社会传播背后的科学秘密,并且告诉......一起来看看 《疯传》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换