当前位置:首页 > 技术 > 后端 > 正文内容

【LeetCode】第289场单周赛 --- 用中等题来骗来偷袭我这个老同志?

anan7天前后端22

目录

Hello朋友们,我是秋刀鱼,一只活跃于Java区与算法区的新人博主~

欢迎大家加入高校算法学习社区: https://bbs.csdn.net/forums/Suanfa,社区里大佬云集,大家互相交流学习!

今天给大家带来LeetCode 289场单周赛的题目解析,并分享一下我解题时的思考过程与犯下的错误。如果觉得还不错的话务必三连支持一下博主哦


主页:秋刀鱼与猫 期待你的支持与关注~

题1: 6070.计算字符串的数字和

题目描述

题目链接

提示:

  • 1 <= s.length <= 100
  • 2 <= k <= 100
  • s 仅由数字(0 - 9)组成。

解题思路

字符串中的每 k 个整数进行加运算可以为一个新的整数,不足 k 个整数的一组在末尾同样可以合并。

实现思路可以使用递归解决第一步判断字符串长度,如果长度小于 k 直接返回,否则执行K个一组的拼接操作并进入下一层递归。

思路还算单这里不过多赘述,大家可以自己动手写一写哦。

代码编写(Java版本)

class Solution { 
public String digitSum(String s, int k) { 
  int len = s.length();
  if (len <= k) { 
      return s;
  }
  StringBuilder str = new StringBuilder();
  int i = 0;
  for (; i + k < len; i += k) { 
      int val = 0;
      for (int j = i; j < i + k; ++j) { 
          val += s.charAt(j) - '0';
      }
      str.append(val);
  }
  int val = 0;
  // 处理最后一组的情况
  for (; i < len; ++i) { 
      val += s.charAt(i) - '0';
  }
  str.append(val);
  return digitSum(str.toString(), k);
}
}

题2: 2244. 完成所有任务需要的最少轮数

题目描述

题目链接

解题思路

题目中说明,每一轮中能够完成 2 个或 3 个同样难度级别的任务,稍加分析可以得知,无法被 2 或 3 整除的任务数量一定无法完成所有的正实数中,无法被 2 或 3 整除的数只有 1 ,因此当某个任务数量为 1 时直接返回 -1 。

对于完成任务需要的最少轮数,运用到贪心的思想:每次尽可能多地完成任务,也就是尽可能在一轮中完成 3 次任务。但是这里需要留意:当 任务数%3 == 1时,最终可能会剩下 4 个任务,因为不能单独完成 1 个任务因此 4 个任务要分成 2、2 来完成。

最终遍历所有任务返回完成任务的轮数之和即是结果值。

代码编写(Java版本)

class Solution { 
 public int minimumRounds(int[] tasks) { 
     // 存放每个任务的数量
     Map<Integer, Integer> taskMap = new HashMap<>();
     for (int val : tasks) { 
         taskMap.put(val, taskMap.getOrDefault(val, 0) + 1);
     }
     int ans = 0;
     for (Map.Entry<Integer, Integer> entry : taskMap.entrySet()) { 
         int val = entry.getValue();
         // 任务数量为 1 代表无法完成,直接返回 -1 
         if (val == 1) { 
             return -1;
         }
         int red = val % 3;
         if (red == 0) { 
             ans += val / 3;
         } else if (red == 1) { 
             ans += (val - 4) / 3 + 2;
         }else{ 
             ans += val / 3 + 1;
         }
     }
     return ans;
 }
}

题3: 2245. 转角路径的乘积中最多能有几个尾随零

题目描述

题目链接

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= grid[i][j] <= 1000

叨叨两句

这道题目我在周赛中挺多的时间,并不是说题目有多难,而是没有注意到 5 因子的数量可能少于 2 因子的数量,在这一点上耽误了太多的时间,也导致最后一题没有时间AC。虽然最后还是A了这道题,但是代码还是又长又臭,心里很不是滋味。

解题思路

前置知识

相信很多朋友都有遇到过乘数的尾数 0 这一类的问题,但是我还是想在这里简单阐述一下。

对于任意两对数的乘法运算,产生的尾数 0 是来源于 2、5 这两个因子相乘,如果没有这两个因子的乘法运算式则无法产生尾数 0 的。

举个栗子:大家都知道 4 ⋅ 25 = 100 4\cdot25 = 100 425=100 100 100 100 后有两个尾数 0 。之所以得到两个尾数 0 是因为 25 25 25 被拆分为 5 ⋅ 5 5\cdot5 55 提供了两个 5 因子,而 4 被分解为 2 ⋅ 2 2\cdot2 22 提供两个 2 因子。这些因子凑成了两对 2 ⋅ 5 2\cdot5 25 的式子因此提供了两个尾数0。

因此乘法运算中尾数 0 的个数等于拆分每一个乘数得到的 5、2 因子数量的最小值。

问题分析

题目中要求找到尾数 0 位数最多的一条转角路径,转角路径指的是一条最多改变一次方向的直线。既然是最多改变一次方向,同样可以不改变方向,但是这一点可以不在讨论的范畴之内,因为尽可能多地走更多的格子才有可能获取更大位数的位数0,这点基于贪心的思想。

既然每一条路径都想要尽可能多地走几步,那么符合要求的路径一定满足下面的要求:

  • 转动一次
  • 一直移动直到边界停止

既然路劲一定会转动一次,那么只需要枚举出所有点的转动情况,求出尾数0位数的最大值即可,例如枚举到下图中黄色表示的格子为转动点:

那么在点的转动一定存在下面四种移动情况:

路径求值

存在也仅存在这四种路径情况,那么现在只需要枚举这四种路径情况上的值,找到每一条路径上的值 5 因子与 2 因子数量的最小值,即是这一条路径的尾数 0 的位数。为了方便计算,我将原数组中每个数值转换为其 5 因子的个数,并定义了一个新的数组存储每一个值的 2 因子数目。

因为害怕超时,在我的代码中使用了前缀和的思想来求因子数目。将一条路径分为横、竖两条,通过预先处理 5 因子、2 因子的前缀和数组的方式来快速获取因子数目,再将两个因子数目进行一个比对,最小值即是该路径尾数 0数量。

代码编写(Java版本)

class Solution { 
 int n, m;
 // 获取 base 因子的数量
 public int check(int val, int base) { 
     if (val % base != 0) { 
         return 0;
     }
     int ret = 0;
     while (val % base == 0) { 
         ++ret;
         val /= base;
     }
     return ret;
 }
 // 处理前缀和数组
 public void build(int[][] preSumLine, int[][] preSumTop, int[][] grid) { 
     for (int i = 0; i < n; ++i) { 
         for (int j = 0; j < m; ++j) { 
             preSumLine[i][j + 1] = grid[i][j];
             preSumLine[i][j + 1] += preSumLine[i][j];

             preSumTop[j][i + 1] = grid[i][j];
             preSumTop[j][i + 1] += preSumTop[j][i];
         }
     }
 }
 public int maxTrailingZeros(int[][] grid) { 
     n = grid.length;
     m = grid[0].length;
     int[][] bygird = new int[n][m];
     for (int i = 0; i < n; ++i) { 
         for (int j = 0; j < m; ++j) { 
             int cur = grid[i][j];
             int num1 = check(cur, 5);
             int num2 = check(cur, 2);
             grid[i][j] = num1;
             bygird[i][j] = num2;
         }
     }
     // 4 个前缀和数组
     int[][] preSumLine = new int[n][m + 1];
     int[][] preSumTop = new int[m][n + 1];
     int[][] presSumLine2 = new int[n][m + 1];
     int[][] preSUmTop2 = new int[m][n + 1];
     build(preSumLine, preSumTop, grid);
     build(presSumLine2, preSUmTop2, bygird);
     int ans = 0;
     for (int i = 0; i < n; ++i) { 
         for (int j = 0; j < m; ++j) { 
             // 判断 4 条路径的逻辑
             int left = preSumLine[i][j + 1];
             int right = preSumLine[i][m] - preSumLine[i][j];
             int left2 = presSumLine2[i][j + 1];
             int right2 = presSumLine2[i][m] - presSumLine2[i][j];

             int top = preSumTop[j][i];
             int bottom = preSumTop[j][n] - preSumTop[j][i + 1];
             int top2 = preSUmTop2[j][i];
             int bottom2 = preSUmTop2[j][n] - preSUmTop2[j][i + 1];

             int leftTop = Math.min(left + top, left2 + top2);
             int rightTop = Math.min(right + top, right2 + top2);
             int leftBottom = Math.min(left + bottom, left2 + bottom2);
             int rightBottom = Math.min(right + bottom, right2 + bottom2);
             ans = Math.max(ans, Math.max(leftTop, Math.max(rightTop, Math.max(leftBottom, rightBottom))));
         }
     }
     return ans;
 }
}

题4: 2246. 相邻字符不同的最长路径

题目描述

题目链接

提示:

  • n == parent.length == s.length
  • 1 <= n <= 105
  • 对所有 i >= 10 <= parent[i] <= n - 1 均成立
  • parent[0] == -1
  • parent 表示一棵有效的树
  • s 仅由小写英文字母组成

解题思路

一道很经典的题目,解题的思路是使用递归来求解。

首先不考虑太多结点,就仅仅考虑一个结点与其子节点的情况:

如果考虑路线经过父节点,那么路线可能会存在下面的两种方式:

现在就这两种路径方式进行讨论:

1、要求相邻的结点要求字符不相同

这点也就是说经过父节点的路径上相邻结点,也就是其左右孩子结点,字符不能与父节点字符相同。如上图所示,左孩子与父节点字符相同,因此任何从左孩子过来的路径都不予考虑。

2、要求题目中要求返回最长的路径

既然经过父节点会存在这两种方式,对于

  • 方式一中路径的长度一定是左右孩子有效路径之和,例如上图中的有效路径只是父节点到右孩子的路径有效,左孩子与父节点相同因此其返回的路径无效。
  • 方式二中既然要求返回最长的路径,那么继续向上传递的路径同样是左右孩子中有效路径最长的那一条路径。

因为路径一定经过父节点,因此方式一、方式二中的路径都需要加上父节点也就是长度+1。

代码编写(Java版本)

class Solution { 
 // 保存 父 -> 子 结点的关系
 List<Integer>[] sons;
 int ans = 0;
 String s;
 int n;
 public int dfs(int idx) { 
     int max = 0;
     // 存放所有有效路径长度
     List<Integer> tmp = new ArrayList<>();
     // 哨兵元素,便于处理
     tmp.add(0);
     tmp.add(0);
     if (sons[idx] != null) { 
         for (int son : sons[idx]) { 
             // 返回子节点向上传递的路径长度
             int value = dfs(son);
             // 判断该路径是否有效
             if (s.charAt(idx) != s.charAt(son)) { 
                 tmp.add(value);
                 max = Math.max(value, max);
             }
         }
     }
     // 排序便于返回
     tmp.sort((a,b)->{ 
         return b - a;});
     // 更新最长路径长度
     ans = Math.max(ans, 1 + tmp.get(0) + tmp.get(1));
     // 返回子节点最长有效路径
     return tmp.get(0) + 1;
 }
 public int longestPath(int[] parent, String _s) { 
     n = parent.length;
     sons = new List[n];
     this.s = _s;
     for (int i = 1; i < n; i++) { 
         if (sons[parent[i]] == null) { 
             sons[parent[i]] = new ArrayList<>();
         }
         sons[parent[i]].add(i);
     }
     dfs(0);
     return ans;
 }
}
,https://blog.csdn.net/qq_51439643/article/details/124259599
打赏
版权声明:所有来源为第三方内容,若本站收录的文章无意侵犯了贵司版权,请给下面邮箱地址来信,我们会及时处理和回复,谢谢。

管理员邮箱:42004990@qq.com

微信公众号

分享给朋友:

相关文章

JVM结构与内存模型

JVM结构与内存模型

JVM结构与内存模型 众所周知JAVA是跨平台的语言咱们通过JAVA C命令编译成的.class文件,一次编译导出运行,首先运行需要什么,我们的JAVA环境,JAVA虚拟机中(JVM),因为JVM...

初学Java-----简单的猜数字小游戏

初学Java-----简单的猜数字小游戏

目录 一·游戏的主要内容和规则 二·实现过程 三·实现结果 一·游戏的主要内容和规则 这个小游戏的主体就是猜数字,首先系统会自己会生成一个数字,然后用户手动进行输入一个数字,将两个数字进行...

初识Java语言(五)- 包和继承

初识Java语言(五)- 包和继承

前面,我们讲了Java中的一些基本的特征,与其他语言也有很多的相似之处。本期文章,我们来看一看在Java中包的概念和继承的概念。大家坐好,我们发车了!!! 前期文章: 前言- IDEA如何配置...

【JavaSE系列】Java面向对象之包与继承

【JavaSE系列】Java面向对象之包与继承

⭐️前面的话⭐️ 本篇文章带大家认识Java基础知识——包与继承,在Java当中一切皆可视为对象,而对象是由类所实例化出来的,将类组织起来那就是一个包,类与类之间是可以存在关联的,例如猫,狗,鸟等动...

字节跳动换老板了,我面试也扑街了...

字节跳动换老板了,我面试也扑街了...

5月20日,字节跳动创始人张一鸣发布内部全员信,宣布卸任CEO一职。字节跳动联合创始人梁汝波将接任成为新CEO。 对于张一鸣的卸任原因,网友们纷纷猜测。有人根据全员信猜测,是不是去年okr完成得...

【JavaP6大纲】Java基础篇:为什么jdk8以后HashMap会使用红黑树优化?

【JavaP6大纲】Java基础篇:为什么jdk8以后HashMap会使用红黑树优化?

为什么jdk8以后HashMap会使用红黑树优化? 在Jdk1.8版本后,Java对HashMap做了改进,在链表长度超过8且数组长度大于64时,将后面的数据存在红黑树中,以加快检索速度。 为什么...