周赛 – 177

1. 日期之间隔几天

请你编写一个程序来计算两个日期之间隔了多少天。
日期以字符串形式给出,格式为 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 年之间的有效日期。

代码

viv丑陋版

我记得以前写这道题好快的……今天不知道是不是因为在边写边吃沙琪玛……debug很久……哭哭……
分别算两个日期距离1970-01-01的天数做差取绝对值。
算的过程就暴力按照月份枚举就行啦,反正也没有多少。
每遍历到一个月就加上对应的天数,如果是统计的最后一个月就加上day。闰年单独判断一下。

int mp[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
class Solution {
public:
    bool isLoop(int year) {
        if((year % 100 != 0 && year % 4 == 0) || year % 400 == 0) return true;
        return false;
    }
    int calculate(string date) {
        int year = (date[0]-'0')*1000 + (date[1]-'0')*100 + (date[2]-'0')*10 + (date[3]-'0');
        int month = (date[5]-'0')*10 + (date[6]-'0');
        int day = (date[8]-'0')*10 + (date[9]-'0');
        int ans = 0;
        for(int i=1970; i<=year; i++) {
            for(int j=1; j<=12; j++) {
                if(i == year && j == month) {
                    ans += day;
                    break;
                }
                else {
                    ans += mp[j-1];
                    if(j == 2 && isLoop(i)) ans++;
                }
            }
        }
        return ans;
    }
    int daysBetweenDates(string date1, string date2) {
        int ans1 = calculate(date1);
        int ans2 = calculate(date2);
        return abs(ans1 - ans2);
    }
};

zz美丽版

我简直想把zz美丽版改成zz丑陋版???不带这么玩的???
再回头看看我的cpp,哦真是思路清晰。

class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        import datetime
        dayA = datetime.datetime.strptime(date1, '%Y-%m-%d')
        dayB = datetime.datetime.strptime(date2, '%Y-%m-%d')
        ans = (dayB - dayA).days
        if ans < 0: ans = -ans
        return ans

2. 验证二叉树

二叉树上有 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

代码

viv丑陋版

看到题目开始思考判断二叉搜的方法,然后想到了统计入度
一棵二叉树只有根节点的入度为0,其余应该都为1。
要想只有一棵二叉树,就必须有且只有一个入度为0的节点并且没有节点的入度不是0或1。
[scode type=”red”]以下代码有误呜呜呜呜……[/scode]

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        int in[n]; memset(in, 0, sizeof(in));
        for(auto v: leftChild) if(v != -1) in[v]++;
        for(auto v: rightChild) if(v != -1) in[v]++;
        
        int zero = 0, noone = 0;
        for(int i=0; i<n; i++) {
            if(in[i] == 0) zero++;
            else if(in[i] != 1) noone++;
        }
        
        if(zero == 1 && noone == 0) return true;
        return false;
    }
};

zz美丽版

zz原来的想法错的居然和我一模一样!
单独一个点再加一个环,也满足一个点入度为0,其余点入度为1的情况。
考虑到题目已经保证所有的节点最多只有两个儿子了,只需判断没有环并且连通块数量为1即可。
想到这里就很简单啦,用并查集判环+数连通块的数量。

const int MAXN = 1e4 + 5;
int fa[MAXN];

int find(int x) {
    return fa[x] = (fa[x] == x ? x : find(fa[x]));
}

bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx == fy) return false;

    if(fx > fy) swap(fx, fy);
    fa[fx] = fy;
    return true;
}

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        for(int i=0; i<n; i++) fa[i] = i;
        int cnt = n;
        for(int i=0; i<n; i++) {
            if(leftChild[i] != -1) {
                if(merge(i, leftChild[i]) == false) return false;
                else cnt--;
            }
            if(rightChild[i] != -1) {
                if(merge(i, rightChild[i]) == false) return false;
                else cnt--;
            }
        }
        return cnt == 1;
    }
};

3. 最接近的因数

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

代码

viv丑陋版

我被这道题卡自闭了……
[scode type=”red”]想了一会觉得没有什么公式,就开始暴力找。
想到从根号附近开始找,然后我就写下了匪夷所思的一行……

for(int i=x; i--; i>=1)

……
并且在找bug的时候自动忽略了这一行可能的错误,我还在想就这么几行代码没道理啊到底哪里错了……
[/scode]
其实思路是对的,就从根号附近开始找,符合条件就记录答案就ok。

class Solution {
public:
    vector<int> closestDivisors(int num) {
        int mn = 1e9 + 5;
        vector<int> ans;
        for(int i=sqrt(num)+2; i>=1; i--) {
            if((num + 1) % i == 0) {
                if(mn > abs(i-(num+1)/i)) {
                    mn = abs(i-(num+1)/i);
                    ans = {i, (num+1)/i};
                }
            }
            if((num + 2) % i == 0) {
                if(mn > abs(i-(num+1)/i)) {
                    mn = abs(i-(num+2)/i);
                    ans = {i, (num+2)/i};
                }
            }
        }
        return ans;
    }
};

zz美丽版

思路一样一样啦。

class Solution {
public:
    vector<int> closestDivisors(int num) {
        int delta = num + 1, a = 1, b = num + 2;
        
        for (long long i = 1; i * i <= num + 2; i++){
            if ((num + 1) % i == 0){
                int d = abs(i - (num + 1) / i);
                if (d < delta) delta = d, a = i, b = (num + 1) / i;
            }
            if ((num + 2) % i == 0){
                int d = abs(i - (num + 2) / i);
                if (d < delta) delta = d, a = i, b = (num + 2) / i;
            }
        }
        
        return {a, b};
    }
};

4. 形成三的最大倍数

给你一个整数数组 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
  • 返回的结果不应包含不必要的前导零。

代码

viv丑陋版

看到题就想到小学老师教的是3的倍数的数字的每一位加起来的和一定是三的倍数。
然后我就开始表演,我把所有的数按照从小到大排序,然后先删小的,删到满足条件为止,成功罚时*1。
毕竟1, 1, 1, 2这种答案就会变成21而不是111……
然后多想了一步,其实最多只需要删两个数字
如果sum % 3 == 1,那么删掉一个x % 3 == 1的x或者x % 3 == 2 && y % 3 == 2的x和y就好。
如果sum % 3 == 2,那么删掉一个x % 3 == 2的x或者x % 3 == 1 && y % 3 == 1的x和y就好。
很显然我们先判断需不需要删,不需要就全用上;如果需要删,先尝试删一个数字;如果删一个数字不行就删两个数字。

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        sort(digits.begin(), digits.end());
        int n  = digits.size(), sum = 0;
        for(int i=0; i<n; i++) sum += digits[i];
        
        bool flag = false;
        if(sum % 3 == 0) flag = true;
        for(int i=0; !flag && i<n; i++) {
            if((sum - digits[i]) % 3 == 0) {
                digits[i] = -1;
                flag = true;
                break;
            }
        }
        for(int i=0; !flag && i<n; i++) {
            for(int j=0; j<i; j++) {
                if((sum - digits[i] - digits[j]) % 3 == 0) {
                    digits[i] = -1; digits[j] = -1;
                    break;
                }
            }
        }
        
        string ans = "";
        if(digits[n-1] == 0) return "0";
        for(int i=n-1; i>=0; i--) if(digits[i]!=-1) ans += digits[i] + '0';
        return ans;
    }
};

zz美丽版

我可以不写这题的zz美丽版吗,zz都说用我的方法做就可以了TAT。
不过能写出这种DP也是神……

const int MAXN = 1e4 + 50;
int dp[15][3];
pair<int, int> pre[15][3];
char ans[MAXN];

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        int n = digits.size();

        int cnt[10];
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++) cnt[digits[i]]++;
        
        memset(dp, -1, sizeof(dp));
        dp[0][0] = cnt[0]; pre[0][0] = make_pair(-1, -1);
        
        for (int i = 1; i <= 9; i++){
            for (int k = cnt[i]; k >= cnt[i] - 2 && k >= 1; k--){
                for (int j = i - 1; j >= 0; j--){
                    for (int c = 0; c < 3; c++){
                        if (dp[j][c] == -1) continue;
                        int nxt = (k % 3 * i % 3 + c) % 3;
                        if (dp[i][nxt] < dp[j][c] + k){
                            dp[i][nxt] = dp[j][c] + k;
                            pre[i][nxt] = make_pair(j, c);
                        }
                    }
                }
            }
        }
        
        int len = 0, start = -1;
        for (int i = 9; i >= 0; i--){
            if (dp[i][0] > len){
                len = dp[i][0];
                start = i;
            }
        }
        
        if (start == -1) return "";
        if (start == 0) return "0";
        
        int curi = start, curk = 0, cur = 0;
        while(curi != -1){
            pair<int, int> prev = pre[curi][curk];
            int curc = 0;
            if (prev.first == -1) 
                curc = dp[curi][curk];
            else
                curc = dp[curi][curk] - dp[prev.first][prev.second];
            
            for (int i = 0; i < curc; i++) ans[cur++] = (curi + '0');
            
            curi = prev.first;
            curk = prev.second;
        }
        ans[len] = 0;
        
        string ret(ans);
        return ret;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇