Leetcode-每日一题【剑指 Offer 13. 机器人的运动范围】

这篇具有很好参考价值的文章主要介绍了Leetcode-每日一题【剑指 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

解题思路

1.题目要求我们求出机器人能够到达多少个格子,对于这道题我们依旧采用深度优先搜索来解决。

2.首先定义一个m行n列的布尔类型的visited数组,用来记录每个格子是否被访问过。然后定义一个dfs方法,用来进行深度优先搜索。在搜索过程中,如果当前格子的行或列小于0,或者大于等于m或n,或者当前格子已经被访问过,或者当前格子的数字之和大于k,则返回0。否则,将当前格子标记为已访问,并返回1加上向右、向下、向左、向上四个方向的dfs调用结果之和。

3.再定义一个sum方法,用来计算一个数字的每一位之和。首先定义一个res变量,并将其初始化为0。然后判断x是否为0,如果不为0,则将res加上x的个位数,并将x除以10。最后返回res。

4.在movingCount方法中,首先初始化类成员变量m、n和k,并创建一个m行n列的visited数组。然后调用dfs方法,从矩阵的左上角开始搜索,并返回结果。

代码实现

class Solution {
    int m;
    int n;
    int k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        visited = new boolean[m][n];
        return dfs(0,0);
    }
    public int dfs(int i, int j){
        if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k<sum(i)+sum (j)){
            return 0;
        }
        visited[i][j] = true;
        return 1 + dfs(i+1,j) + dfs(i,j+1) + dfs(i-1,j) + dfs(i,j-1);

    }
    int sum(int x){
        int res = 0;
        while(x != 0){
            res = res +(x % 10);
            x = x / 10;
        }
        return res;
    }
}

测试结果

Leetcode-每日一题【剑指 Offer 13. 机器人的运动范围】,算法每日一题,leetcode,算法,深度优先,java

 文章来源地址https://www.toymoban.com/news/detail-640693.html

到了这里,关于Leetcode-每日一题【剑指 Offer 13. 机器人的运动范围】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指 Offer !!13. 机器人的运动范围(回溯算法)

    剑指 Offer 13. 机器人的运动范围 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能

    2024年02月11日
    浏览(38)
  • 剑指Offer13.机器人的运动范围 C++

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

    2024年02月10日
    浏览(34)
  • 剑指offer(C++)-JZ13:机器人的运动范围(算法-回溯)

    作者:翟天保Steven 版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处 题目描述: 地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,

    2024年02月12日
    浏览(46)
  • 剑指offer12 矩阵中的路径 13 机器人的运动范围 34.二叉树中和为某一值得路径

    //写的有点问题,暂时想不到怎么改,先放着,通过用例71/83 卡住的是abcd 但是改了又有问题 无语 看了 答案 都写不对 在类成员里面定义了row和col 就不要重复定义了 不然不知道为什么就开始发疯 先贴出蠢货写出来的东西 审题也审不明白 机器人只能上下左右走 不能一行一行

    2024年02月15日
    浏览(37)
  • Leetcode-每日一题【剑指 Offer 16. 数值的整数次方】

    实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。 示例 1: 输入: x = 2.00000, n = 10 输出: 1024.00000 示例 2: 输入: x = 2.10000, n = 3 输出: 9.26100 示例 3: 输入: x = 2.00000, n = -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25 提示: -10

    2024年02月13日
    浏览(38)
  • Leetcode-每日一题【剑指 Offer 29. 顺时针打印矩阵】

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1: 输入: matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] 限制: 0 = matrix.length = 100 0 = matrix[i].length = 100 1.题目要求

    2024年02月13日
    浏览(57)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)
  • (字符串 ) 剑指 Offer 05. 替换空格 ——【Leetcode每日一题】

    难度:简单 请实现一个函数,把字符串 s 中的每个 空格 替换成 “ %20 ”。 示例 1: 输入:s = “We are happy.” 输出:“We%20are%20happy.” 限制 : 0 = s 的长度 = 10000 💡思路:双指针法 如果想把这道题目做到 极致 ,就不要只用额外的辅助空间了! 首先扩充数组到每个空格替换

    2024年02月08日
    浏览(60)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(39)
  • Leetcode-每日一题【剑指 Offer 26. 树的子结构】

    输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构, 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A:      3     /    4   5   /  1   2 给定的树 B:    4    /  1 返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点

    2024年02月13日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包