LeetCode第177场周赛

论熟练调库的重要性😹排名 89 / 2985

第一题:日期之间隔几天

  请你编写一个程序来计算两个日期之间隔了多少天。
    
  日期以字符串形式给出,格式为 YYYY-MM-DD,如示例所示。
   
  示例 1:
  输入:date1 = “2019-06-29”, date2 = “2019-06-30”
  输出:1
  
  示例 2:
  输入:date1 = “2020-01-15”, date2 = “2019-12-31”
  输出:15

思路:
  自己写挺麻烦的,可以用一个数组记录每个月的天数,计算时还要考虑闰年(每4年是闰年,但是100的倍数又不是闰年,400的倍数又是闰年😒),所以我就直接调库了…。

代码:

第二题:验证二叉树

  二叉树上有 n 个节点,按从 0 到 n – 1 编号,其中节点 i 的两个子节点分别是 leftChild[i] 和 rightChild[i]。
  
  只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时,返回 true;否则返回 false。
  
  如果节点 i 没有左子节点,那么 leftChild[i] 就等于 -1。右子节点也符合该规则。
  
  注意:节点没有值,本问题中仅仅使用节点编号。
  
  示例 1:  
  输入:n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
  输出:true
  
  示例 2:
  输入:n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
  输出:false
  
  示例 3:  
  输入:n = 2, leftChild = [1,0], rightChild = [-1,-1]
  输出:false
  
  示例 4:  
  输入:n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1]
  输出:false

思路:
  这题考察的其实是对二叉树的理论知识的掌握,并不需要真的构建出二叉树。
  1. 在树中只有1个根结点,所以没有父结点的结点数只能为1;
  2. 一个结点如果已经有了父结点,就不能再有其他父结点,(所以leftChildrightChild中不能有重复的结点)。
  3. 用childs表示有父结点的结点集合,则childs.size()应该等于n-1
  4. 依次访问leftChildrightChild中的元素,如果不为-1且未在childs中出现则加入到childs中。

代码:

第三题:最接近的因数

  给你一个整数 num,请你找出同时满足下面全部要求的两个整数:
  
  两数乘积等于  num + 1 或 num + 2
  以绝对差进行度量,两数大小最接近
  你可以按任意顺序返回这两个整数。
  
  示例 1:
  输入:num = 8
  输出:[3,3]
  解释:对于 num + 1 = 9,最接近的两个因数是 3 & 3;对于 num + 2 = 10, 最接近的两个因数是 2 & 5,因此返回 3 & 3 。
  
  示例 2:
  输入:num = 123
  输出:[5,25]
  
  示例 3:
  输入:num = 999
  输出:[40,25]

思路:
  将num + 1num + 2拆分为最接近 int(\sqrt{num+1})int(\sqrt{num+2}) 的两个因子相乘。

代码:

第四题:形成三的最大倍数

  给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。
  
  由于答案可能不在整数数据类型范围内,请以字符串形式返回答案。
  
  如果无法得到答案,请返回一个空字符串。
  
  示例 1:
  输入:digits = [8,1,9]
  输出:”981″
  
  示例 2:
  输入:digits = [8,6,7,1,0]
  输出:”8760″
  
  示例 3:
  输入:digits = [1]
  输出:””
  
  示例 4:
  输入:digits = [0,0,0,0,0,0]
  输出:”0″

思路:
  这题的要求是组合出最大的数字,怎么样组合的数字最大呢?当然是位数越多越好。位数相同时,大的数字在前,小的数字在后。如果digits本身就是3的倍数,那当然最好,直接按降序排列即可;否则要去掉1~2个数字,才能构成3的倍数。所以总体的目标是在digits中去掉最少的数构成一个3的倍数。
  具体算法如下:
  1. 将digits按降序排列,(记为digits_desc)。
  2. 将digits_desc中的每个元素对3取模,记为m_list
  3. 将m_list元素之和对3取模,记为m
  4. 如果m为0,则digits_desc本身组成的数即为最大的3的倍数;如果m不为0,先尝试去掉1个(尽量小的)数能否变成3的倍数:在m_list中寻找有没有等于m的数,如果有,将digits_desc中对应元素去掉,组成的数即为结果。
  5. 如果去掉1个数无法组成3的倍数,则需要去掉2个数,m为1时需在m_list中去掉2个2,m为2时需在m_list中去掉2个1。

示例 2: [8,6,7,1,0]
  1. [8,6,7,1,0] => [8,7,6,1,0]
  2. [8,7,6,1,0] => [2,1,0,1,0]
  3. [2,1,0,1,0] => 1 ,不为0
  4. 搜索 [2,1,0,1,0], 去掉下标为3的1即可变成3的倍数,[8,7,6,1,0]去掉下标为3的数,结果为8760。

示例 5: [2,2,3]
  1. [2,2,3] => [3,2,2]
  2. [3,2,2] => [0,2,2]
  3. [0,2,2] => 1 ,不为0
  4. 搜索 [0,2,2], 其中没有1,因此去掉1个数无法组成3的倍数。
  5. 在[3,2,2]中去掉2个2,组成3的倍数,结果为3。

: 对0和空要注意一下输出格式。

代码: