Leetcode周赛:177

第 177 场周赛


Problem 1360: 日期之间间隔几天

       直接调用库函数即可。

import java.time.LocalDate;
import java.time.temporal.ChronoUnit;
class Solution {
    public int daysBetweenDates(String date1, String date2) {
        return (int) Math.abs(LocalDate.parse(date1).until(LocalDate.parse(date2), ChronoUnit.DAYS));
    }
}

       使用 $LocalDate$ 类及其 $until(\ )$ 方法,使用 $ChronoUnit.DAYS$ 常量表明以天为单位计算。在此要注意的是Leetcode并没有默认导入 $java.time$ 类,因此要自己导入。


Problem 1361: 验证二叉树

       利用二叉树的性质可以知道,二叉树根节点外每个节点有且只有一个父节点,并且有且只有一个根节点。通过这个性质,我们可以遍历数组,找到所有的节点的父节点,再验证是否符合上述性质。

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] parent = new int[n]; //储存每个节点的父节点
        Arrays.fill(parent, -1);
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1)
                if (parent[leftChild[i]] == -1) parent[leftChild[i]] = i;
                else return false; //如果该节点已有父节点,则非二叉树
            if (rightChild[i] != -1)
                if (parent[rightChild[i]] == -1) parent[rightChild[i]] = i;
                else return false;
        }
        int cnt = 0;
        for (int i : parent) if (i == -1 && ++cnt > 1) return false; //如果有多个根节点,则非二叉树
        return cnt == 1;
    }
}

Problem 1362: 最接近因数

       显然,如果是平方数的话,题解便是其平方根。而对于非平方数,我们可以对其开方。只要知道一个因数,即可算出另一个因数,因此只需要向一个方向遍历即可。在此我采取向 $0$ 遍历的方法。

class Solution {
    public int[] closestDivisors(int num) {
        int t1 = num + 1, t2 = num + 2; //t1, t2分别为所求目标
        for (int i = (int) Math.sqrt(num) + 1; i > 0; i--)
            if (t1 % i == 0) return new int[] {i, t1 / i};
            else if (t2 % i == 0) return new int[] {i, t2 / i};
        return new int[] {1, t1};
    }
}

Problem 1363: 形成三的最大倍数

参考题解

       第一眼看到这道题的直觉是排序然后遍历。不过这个方案立马被排除了,因为这道题要找的是最大的数,而对于数字的大小,位数比每个数字的大小更重要,因此排序并不是必要的。
       再考察三的倍数的规律。一个数为三的倍数当且仅当其各个位上的数字的和为三的倍数。因此对于 $digits[\ ]$ 数组,如果其和为三的倍数,我们只需要将其所有的数字从大到小排序后输出即可;如果不为三的倍数,则分两种情况,模三余一和模三余二。对于模三余一,如果数组中存在任意一个模三余一的数,只需删去该数即可;如果不存在,则需要删去两个模三余二的数;同理,对于模三余二的情况,则需要删去一个模三余二的数或者两个模三余一的数。最后在输出结果时,唯一要注意的特殊情况是为 $0$ 的情况,毕竟多个 $0$ 并列并不是数字。

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        StringBuilder res = new StringBuilder();
        int sum = 0, //所有数字的和
            mod = 0, //sum % 3 的值
            count = 0; //应该去除的余数为 mod 的数字的个数
        int[] num = new int[10], //每个数字的个数
              mods = new int[3]; //每个数字余数的个数
        for (int i : digits) {
            num[i]++;
            mods[i % 3]++;
            sum += i;
        }
        int remain = sum % 3;
        if (remain == 1) {
            if (mods[1] > 0) { //是否存在模三余一的数
                mod = count = 1;
            } else { //不存在模三余一的数
                mod = 2;
                count = 2;
            }
        } else if (remain == 2) {
            if (mods[2] > 0) {
                mod = 2;
                count = 1;
            } else {
                mod = 1;
                count = 2;
            }
        }
        for (int i = 0; i < 10; i++)
            for (int j = 0; j < num[i]; j++)
                if (count > 0 && mod == i % 3) count--;
                else res.append(i);
        if (res.length() > 0 && res.charAt(res.length() - 1) == '0') return "0"; //处理 0
        return res.reverse().toString();
    }
}