前端工程师的 LeetCode 之旅 - 177周赛

413 阅读3分钟
原文链接: mp.weixin.qq.com
01      5169.日期之间相隔几天 题目描述【Easy】 请你编写一个程序来计算两个日期之间相隔多少天。 日期以字符串的形式给出,格式为 YYYY-MM-DD。

本道题主要考察日期格式之间的转化,特别需要注意的地方就是月份在计算机的世界里是从0开始计数的

02                5170.验证二叉树 题目描述【Medium】 二叉树上有 n 个节点,按从 0 到 n - 1 编号,其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。 只有所有节点能够形成且只形成一颗有效的二叉树,返回 true;否则返回 false。 如果节点 i 没有左子节点,那么 leftChild[i] 就等于 -1。右子节点也符合该规则。 注意:节点没有值,本问题中仅仅使用节点编号。

由于二叉树是递归定义的,所以一般二叉树的题目也都会采用递归的方法去处理,逻辑上更容易理解。

解决本道题的关键在于如何验证以下两个条件:

  • 二叉树合法。【递归遍历过程中利用哈希表记录子节点状态】

  • 只形成一颗二叉树。【递归遍历结束后哈希表中子节点的个数】

03             5171.最接近的因数 题目描述【Medium】 给你一个整数 num,请你找出同时满足下面全部要求的两个整数: 1、两数乘积等于 num + 1 或 num + 2; 2、以绝对差进行度量,两数大小最接近; 你可以按照任意顺序返回这两个整数。

本道题主要考察基础的数学知识,解题的关键有以下两点:

  • 利用除法进行消元操作。

  • 两个因数中的最小值不会大于乘积的开根号。

04         5172.形成三的最大倍数 题目描述【Hard】 给你一个整数数组 digits,你可以通过按任意顺序连续其中某些数字来形成 3 的倍数,请你返回所得到的最大的 3 的倍数。 由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。 如果无法得到答案,请返回一个空的字符串。

本题同样是一道数学相关的题型。

如果 digits 所有整数的和能被3整除,那么它们所组成的字符串一定能够被3整除。

如果不能被3整除,那么有以下两种情况:

  • sum % 3 === 1

  • sum % 3 === 2

对于这两种情况,需要对 sum 进行加减操作,在本道题目中,只能考虑减操作。

以 22 为例,可以对其减去一个取余为1的数【1,4,7】,例如:(22 - 1)%  3 === 0。

也可以减去两个取余为2的数【2,5,8】,例如:(22 - 2 - 5)%  3 === 0。

本道题中,要保持最终生成的字符串的值最大,那么应该优先考虑减去一个取余为1的数。

对于第二种情况,那么就可以减去1个取余为2的数【2,5,8】,或者减去2个取余为1的数【1,4,7】。

最后,将剩余的整数按照从大到小顺序拼接字符串即可。

05 往期回顾

你点的每个赞,我都认真当成了喜欢