LeetCode第177场周赛

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

Contents

1 第一题：日期之间隔几天
2 第二题：验证二叉树
3 第三题：最接近的因数
4 第四题：形成三的最大倍数

第一题：日期之间隔几天

　　请你编写一个程序来计算两个日期之间隔了多少天。
　　　
　　日期以字符串形式给出，格式为 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的倍数又是闰年😒)，所以我就直接调库了…。

代码：

class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        import datetime
        fmt = "%Y-%m-%d"
        time_1 = datetime.datetime.strptime(date1, fmt)
        time_2 = datetime.datetime.strptime(date2, fmt)
        return abs((time_2 - time_1).days)

class Solution:

def daysBetweenDates(self, date1: str, date2: str) -> int:

import datetime

fmt = "%Y-%m-%d"

time_1 = datetime.datetime.strptime(date1, fmt)

time_2 = datetime.datetime.strptime(date2, fmt)

return abs((time_2 - time_1).days)

第二题：验证二叉树

　　二叉树上有 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. 一个结点如果已经有了父结点，就不能再有其他父结点，(所以leftChild和rightChild中不能有重复的结点)。
　　3. 用childs表示有父结点的结点集合，则childs.size()应该等于n-1。
　　4. 依次访问leftChild和rightChild中的元素，如果不为-1且未在childs中出现则加入到childs中。

代码：

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<bool> b(n);
        for (int i=0;i<n;i++){
            b[i] = false;
        }
        set<int>childs;  // childs维护的是有父节点的结点
        for (int i=0;i<n;i++){
            if(leftChild[i]!=-1){
                if (childs.count(leftChild[i]) == 1)
                    return false;  // 第i个结点有多个父结点 返回false
                childs.insert(leftChild[i]);
            }

        }
        for (int i=0;i<n;i++){
            if(rightChild[i]!=-1){
                if (childs.count(rightChild[i]) == 1)
                    return false; // 第i个结点有多个父结点 返回false
                childs.insert(rightChild[i]);
            }
        }
        if(childs.size() != n-1)
            return false;  // 总共有n个结点，只有1个结点没有父节点，所以有父节点的结点数应该为n-1
        return true;      
    }
};

class Solution {

public:

bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {

vector<bool> b(n);

for (int i=0;i<n;i++){

b[i] = false;

}

set<int>childs; // childs维护的是有父节点的结点

for (int i=0;i<n;i++){

if(leftChild[i]!=-1){

if (childs.count(leftChild[i]) == 1)

return false; // 第i个结点有多个父结点返回false

childs.insert(leftChild[i]);

}

for (int i=0;i<n;i++){

if(rightChild[i]!=-1){

if (childs.count(rightChild[i]) == 1)

return false; // 第i个结点有多个父结点返回false

childs.insert(rightChild[i]);

}

if(childs.size() != n-1)

return false; // 总共有n个结点，只有1个结点没有父节点，所以有父节点的结点数应该为n-1

return true;

}

};

第三题：最接近的因数

　　给你一个整数 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 + 1和num + 2拆分为最接近 $int(\sqrt{num+1})$ 和 $int(\sqrt{num+2})$ 的两个因子相乘。

代码：

class Solution:
    def closestDivisors(self, num: int) -> List[int]:
        def handle(n):
            sqr = int(math.sqrt(n))
            for i in range(sqr, 0, -1):
                if n % i == 0:
                    return i, n//i

        a1, b1 = handle(num+1)
        d1 = abs(a1-b1)
        a2, b2 = handle(num+2)
        d2 = abs(a2-b2)
        if d1 < d2:
            return a1, b1
        else:
            return a2, b2

class Solution:

def closestDivisors(self, num: int) -> List[int]:

def handle(n):

sqr = int(math.sqrt(n))

for i in range(sqr, 0, -1):

if n % i == 0:

return i, n//i

a1, b1 = handle(num+1)

d1 = abs(a1-b1)

a2, b2 = handle(num+2)

d2 = abs(a2-b2)

if d1 < d2:

return a1, b1

else:

return a2, b2

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

　　给你一个整数数组 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和空要注意一下输出格式。

代码：

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits = sorted(digits, reverse=True)
        m_list = [i % 3 for i in digits]
        m = sum(m_list) % 3
        excepts = set()  # 要去掉的数的下标
        if m != 0:
            flag = False  # 记录去掉1个数行不行
            for i in range(len(digits)-1, -1, -1):
                if m_list[i] == m:
                    excepts.add(i)
                    flag = True
                    break
            if not flag:  # 去掉1个数不行，尝试去掉两2数
                count = 0
                if m == 2:
                    for i in range(len(digits)-1, -1, -1):
                        if m_list[i] == 1:
                            excepts.add(i)
                            count += 1
                            if count == 2:
                                break

                elif m == 1:
                    for i in range(len(digits)-1, -1, -1):
                        if m_list[i] == 2:
                            excepts.add(i)
                            count += 1
                            if count == 2:
                                break

        ans = ''
        # 数组转字符串
        for i in range(len(digits)):
            if i not in excepts:
                ans += str(digits[i])

        if ans == '':
            return ''
        ans = ans.lstrip('0')
        if ans == '':
            ans = '0'
        return ans

class Solution:

def largestMultipleOfThree(self, digits: List[int]) -> str:

digits = sorted(digits, reverse=True)

m_list = [i % 3 for i in digits]

m = sum(m_list) % 3

excepts = set() # 要去掉的数的下标

if m != 0:

flag = False # 记录去掉1个数行不行

for i in range(len(digits)-1, -1, -1):

if m_list[i] == m:

excepts.add(i)

flag = True

break

if not flag: # 去掉1个数不行，尝试去掉两2数

count = 0

if m == 2:

for i in range(len(digits)-1, -1, -1):

if m_list[i] == 1:

excepts.add(i)

count += 1

if count == 2:

break

elif m == 1:

for i in range(len(digits)-1, -1, -1):

if m_list[i] == 2:

excepts.add(i)

count += 1

if count == 2:

break

ans = ''

# 数组转字符串

for i in range(len(digits)):

if i not in excepts:

ans += str(digits[i])

if ans == '':

return ''

ans = ans.lstrip('0')

if ans == '':

ans = '0'

return ans