内容简介:这道题本质还是搜索,因此可以使用深度优先搜索和广度优先搜索进行解决。<!-- 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]
开始的,所以可以想象成根节点往子节点或兄弟节点的遍历方式,深度优先搜索就是先遍历子节点,子节点遍历完成后,在遍历兄弟节点。
终止条件应该有:
- 坐标越界,也就是
x >= m
或者y >= n
。 - 该点已经访问过,既然访问过,自然不用重新计算。
- 坐标数字之和大于
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)
那么上面的代码还有可以优化的地方,这个就留给大家去完成了。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题本质还是搜索,因此可以使用深度优先搜索和广度优先搜索进行解决。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
公众号:健程之道
以上所述就是小编给大家介绍的《剑指offer 13——机器人的运动范围》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 使用golang写一个高性能端口扫描器,支持IP范围,端口号范围
- jQuery日期范围选择器
- ThinkPHP模板范围判断标签使用
- JavaScript生成指定范围的时间列表
- [译] Ruby 2.6 增加无穷范围
- 保持安全控制范围成功保护混合云
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。