从零学算法 (剑指 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
原题链接文章来源地址https://www.toymoban.com/news/detail-672684.html

  • 我的思路:从左上角 [0,0] 开始 dfs,如果行列坐标的数位之和大于 k 就返回 0,如果来过了这个点也返回 0,如果超出边界了也返回 0,否则就算是一个能够到达的格子,返回 1+dfs(往右走)+dfs(往下走)。因为是从左上角开始,所以往右和往下足以遍历每个格子。
  •   int M,N,K;
      Set<Integer> set = new HashSet<>();
      public int movingCount(int m, int n, int k) {
          M=m;
          N=n;
          K=k;
          return dfs(0,0);
      }
      public int dfs(int x,int y){
      	// 超出边界
          if(x>=M || y>=N)return 0;
          // 不符题意
          if(getNum(x,y)>K)return 0;
          // 已计算过
          if(set.contains(x*N+y))return 0;
          set.add(x*N+y);
          int ans = dfs(x+1,y)+dfs(x,y+1)+1;
          return ans;
      }
      // 获取格子行列数位和
      public int getNum(int x,int y){
          int ans = 0;
          while(x>0){
              ans+=x%10;
              x/=10;
          }
          while(y>0){
              ans+=y%10;
              y/=10;
          }
          return ans;
      }
    
  • 他人题解:获取格子行列数位和这部分可以优化,以下用 sum 代替一个数的数位和 。一个数在递增的时候,只要没满十,规律都是 sum(x)=sum(x-1)+1,比如 16 和 17 和 18 的 sum 就是 7->8->9。如果满十进一了,就相当于把原本的 9 变成了 0,之前的一位加了 1,算下来就是减少了 8,所以此时 sum(x) = sum(x-1)-8,总结一下就是 sum(x) = x%10==0?s(x-1)-8:sum(x-1)+1。也就是说一个坐标的行列在变化时,他的数位和就能根据这个规律来计算,所以在 dfs 的入参中加入坐标 [i,j] 对应的 sum(i) 和 sum(j),就能递推得到一个坐标的数位和。
  •   int m,n,k;
      // 用数组判断是否来过某个点更快
      boolean[][] see;
      public int movingCount(int m, int n, int k) {
          this.m=m;this.n=n;this.k=k;
          this.see = new boolean[m][n];
          return dfs(0,0,0,0);
      }
      public int dfs(int x,int y,int sx,int sy){
          if(x>=m || y>=n || sx+sy>k || see[x][y])return 0;
          see[x][y]=true;
          int newSx = (x+1)%10==0?sx-8:sx+1;
          int newSy = (y+1)%10==0?sy-8:sy+1;
          int ans = dfs(x+1,y,newSx,sy)+dfs(x,y+1,sx,newSy)+1;
          return ans;
      }
    
  • 他人题解2:既然是遍历每个格子,那其实 bfs 也行,原理都一样,就不赘述了
  •   public int movingCount(int m, int n, int k) {
          boolean[][] visited = new boolean[m][n];
          int res = 0;
          Queue<int[]> queue= new LinkedList<int[]>();
          // 熟悉的 dfs 入参,坐标以及坐标对应的 sum
          queue.add(new int[] { 0, 0, 0, 0 });
          while(queue.size() > 0) {
              int[] x = queue.poll();
              int i = x[0], j = x[1], si = x[2], sj = x[3];
              // 相当于 dfs 的 return 0
              if(i >= m || j >= n || k < si + sj || visited[i][j]) continue;
              visited[i][j] = true;
              // 以下三行相当于 return dfs(下)+dfs(右)+1
              res ++;
              queue.add(new int[] { i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj });
              queue.add(new int[] { i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8 });
          }
          return res;
      }
    

到了这里,关于从零学算法 (剑指 Offer 13)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(47)
  • 剑指 Offer 13. 机器人的运动范围

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

    2024年02月14日
    浏览(51)
  • 剑指 Offer !!13. 机器人的运动范围

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

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

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

    2024年02月10日
    浏览(36)
  • 二叉树(中)+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”

    各位CSDN的uu们你们好呀,今天继续数据结构与算法专栏中的二叉树,下面,让我们进入二叉树的世界吧!!! 二叉树(上)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客 二叉树链式结构的实现 二叉树链式结构的实现 求二叉树的高度 但是这种写法有很大的问题

    2024年02月17日
    浏览(39)
  • 【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 剑指 Offer 60. n个骰子的点

    2023年04月19日
    浏览(57)
  • 【LeetCode: 剑指 Offer II 089. 房屋偷盗(打家窃舍) | 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 剑指 Offer II 089. 房屋偷盗

    2024年02月02日
    浏览(45)
  • 从零学算法79

    79 .给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使

    2024年02月11日
    浏览(33)
  • 从零学算法34

    34 .给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 示例 1: 输入:nums = [5,7,7,8,8,10], target

    2024年02月13日
    浏览(37)
  • 从零学算法55

    55 .给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。 示例 1: 输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标

    2024年02月21日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包