On the shoulders of giants.

weekly-contest-177

日期之间隔几天

请你编写一个程序来计算两个日期之间隔了多少天。

日期以字符串形式给出,格式为 YYYY-MM-DD,如示例所示。

示例 1:

输入:date1 = "2019-06-29", date2 = "2019-06-30"
输出:1

示例 2:

输入:date1 = "2020-01-15", date2 = "2019-12-31"
输出:15

提示:

  • 给定的日期是 1971 年到 2100 年之间的有效日期。
题解

注意闰年和平年,然后用区间减法计算出结果。

时间复杂度:\(O(n)\)

class Solution {
public:
    int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    bool isLeap(int x) {
        return (x % 4 == 0 && x % 100 != 0) || (x % 400 == 0);
    }
    int solve(string date) {
        int year = atoi(date.substr(0, 4).c_str());
        int mon = atoi(date.substr(5, 2).c_str());
        int day = atoi(date.substr(8, 2).c_str());
        int result = 0;
        for(int i = 1971; i < year; i++) {
            result += (isLeap(i) ? 366 : 365);
        }
        days[1] = (isLeap(year) ? 29 : 28);
        for(int i = 0; i < mon - 1; i++) {
            result += days[i];
        }
        return result + day;
    }
    int daysBetweenDates(string date1, string date2) {
        return abs(solve(date2) - solve(date1));
    }
};

验证二叉树

二叉树上有 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 <= n <= 10^4
  • leftChild.length == rightChild.length == n
  • -1 <= leftChild[i], rightChild[i] <= n - 1
题解

建立有向图,然后从根开始遍历(根不为一则无解)。

使用深搜,看是否能走完,是否有回边。

时间复杂度:\(O(n)\)

const int N = 1E4 + 5;
class Solution {
public:
    vector<int> g[N];
    vector<int> vis;
    bool dfs(int x) {
        vis[x] = true;
        for(int i = 0; i < g[x].size(); i++) {
            int y = g[x][i];
            if(vis[y] == 1) return true;
            if(dfs(y)) return true;
        }
        return false;
    }
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> In(n);
        vis.resize(n);
        for(int i = 0; i < n; i++) {
            if(leftChild[i] != -1) {
                In[leftChild[i]]++;
                g[i].push_back(leftChild[i]);
            }
            if(rightChild[i] != -1) {
                In[rightChild[i]]++;
                g[i].push_back(rightChild[i]);
            }
        }
        int root = -1;
        for(int i = 0; i < n; i++) {
            if(In[i] != 0) continue;
            if(root == -1) root = i;
            else return false;
        }
        return root == -1 ? false : !dfs(root);
    }
};

最接近的因数

给你一个整数 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]

提示:

  • 1 <= num <= 10^9
题解

取根号后,根据单调性进行模拟。

时间复杂度:\(O(\sqrt n)\)

class Solution {
public:
    bool check(long long s, int num) {
        return s == num + 1 || s == num + 2;
    }
    vector<int> closestDivisors(int num) {
        int a = ceil(sqrt(num)), b = a;
        if(check(a * b, num)) return vector<int> {a, b};
        while(true) {
            while(1ll * a * b <= num) b++;
            if(check(1ll * a * b, num)) break;
            a--, b--;
        }
        return vector<int> {a, b};
    }
};

形成三的最大倍数

给你一个整数数组 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"

提示:

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9
  • 返回的结果不应包含不必要的前导零。
题解

首先,我们推导等式,设 \(n=b_{m-1}b_{m-2}b_{m-3}\cdots b_1b_0\) ,\(b_i\) 表示第 i 位的数。

\( 10 \mod 3 = 1,10^i \mod 3 = 1\)

\(n\mod 3=\sum_{i=0}^{m-1} b_i\cdot 10^i \mod 3 = \sum_{i=0}^{m-1} b_i \mod3\)

所以,一个数能被 3 整除,可以推出这个数的每个位数之和也能被 3 整除,我们接下来考虑位数。

如果余数为 1 ,我们可以删除一个模 3 余数为 1 的数或者删除两个模 3 余数为 2 的数。

如果余数为 2 ,我们可以删除一个模 3 余数为 2 的数或者删除两个模 3 余数为 1 的数。

时间复杂度:\(O(\log n)\)

class Solution {
public:
    vector<int> count;
    string result;
    bool sub(int x) {
        for(int i = x; i <= 9; i += 3) {
            if(count[i] == 0) continue;
            count[i]--;
            return true;
        }
        return false;
    }
    string largestMultipleOfThree(vector<int>& digits) {
        int n = digits.size(), sum = 0;
        count.resize(10);
        for(auto x : digits) count[x]++, sum += x;
        if(count[0] == n) return "0";
        if(sum % 3 == 1) if(!sub(1)) sub(2), sub(2);
        if(sum % 3 == 2) if(!sub(2)) sub(1), sub(1);
        for(int i = 9; 0 <= i; i--) {
            while(count[i]--) result += '0' + i;
        }
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注