专栏首页GiantPandaCV力扣 第 177 场周赛 题解

力扣 第 177 场周赛 题解

2个月前攒够了衣服就没打了,重新捡起来,被吊打。。

在这里插入图片描述

日期之间隔几天

  • 题面:

第一题

  • 思路:主要是考虑一下闰年和平年,以及每个月有多少天,简单的模拟题。
  • 代码:
bool runnian(int a){
    if(a%400 == 0 || (a%4==0 && a%100 != 0)) return 1;
    else return 0;
}
int dijitian(int a,int b,int c){
    int sum=c;
    for(int i=1;i<b;i++){
        if(i==1||i==3||i==5||i==7||i==8||i==10||i==12)
            sum+=31;
        if(i==4||i==6||i==9||i==11)
            sum+=30;
        if(i==2){
            if(runnian(a)) sum+=29;
            else sum+=28;
        }
    }
    return sum;
}

class Solution {
public:
    int daysBetweenDates(string date1, string date2) {
        int y1 = 0, m1 = 0, d1 = 0;
        int y2 = 0, m2 = 0, d2 = 0;
        y1 = (date1[0]-'0')*1000+(date1[1]-'0')*100+(date1[2]-'0')*10+(date1[3]-'0');
        m1 = (date1[5]-'0')*10+(date1[6]-'0');
        d1 = (date1[8]-'0')*10+(date1[9]-'0');

        y2 = (date2[0]-'0')*1000+(date2[1]-'0')*100+(date2[2]-'0')*10+(date2[3]-'0');
        m2 = (date2[5]-'0')*10+(date2[6]-'0');
        d2 = (date2[8]-'0')*10+(date2[9]-'0');
        int ans=0;
        if(y1==y2)
            ans = abs(dijitian(y1,m1,d1)-dijitian(y2,m2,d2));
        else{
            if(y1>y2){
                swap(y1,y2);
                swap(m1,m2);
                swap(d1,d2);
            }
            for(int i=y1+1;i<y2;i++){
                if(runnian(i))
                    ans+=366;
                else ans+=365;
            }
            ans+=dijitian(y2,m2,d2);
            if(runnian(y1)) ans+=(366-dijitian(y1,m1,d1));
            else ans+=(365-dijitian(y1,m1,d1));
        }
        return ans;
    }
};

验证二叉树

  • 题面:

第二题

  • 数据范围:1 <= n <= 10^4leftChild.length == rightChild.length == n-1 <= leftChild[i], rightChild[i] <= n - 1
  • 思路:这个题呢,需要稍微想一下,其实直接判断一下二叉树的每个节点入度和出度的取值是否合理,并且判断根节点(入度为0的节点)是否唯一就可以了。
  • 复杂度:O(n)
  • 代码:
class Solution {
public:
    int in[10010], out[10010];
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        for(int i=0; i<n; i++){
            out[i]++;
            if(leftChild[i]!=-1) in[leftChild[i]]++;
            if(rightChild[i]!=-1) in[rightChild[i]]++;
        }
        int root = 0;
        bool flag = true;
        for(int i=0; i<n; i++){
            if(in[i]==0) root++;
            if(in[i]>1) flag=false;
            if(out[i]>2) flag=false;
        }
        if(root==1&&flag) return true;
        else return false;
    }
};

最接近的因数

  • 题面:

第3题

  • 思路:暴力题,直接把所有的因子对枚举出来,放到一个vector中,然后按照因子对的绝对值差从小到大排序之后取第1个因子对就可以了。所谓因子对就是对于(a,b),如果a=num/b,那么(a,b)就是因子对。
  • 复杂度:O(2*sqrt(num))
  • 代码:
class Solution {
public:
    struct node{
        int x,y;
        node(){}
        node(int x_,int y_):x(x_),y(y_){}
        bool operator<(const node&rhs) const{
            return abs(x-y) < abs(rhs.x-rhs.y);
        }
    };
    vector<int> closestDivisors(int num) {
        int n = num+1;
        vector<node>v;
        for(int i=1; i*i<=n; i++){
            if(n%i==0){
                v.push_back(node(i,n/i));
            }
        }
        n=num+2;
        for(int i=1; i*i<=n; i++){
            if(n%i==0){
                v.push_back(node(i,n/i));
            }
        }
        sort(v.begin(), v.end());
        vector <int> ans;
        ans.push_back(v[0].x);
        ans.push_back(v[0].y);
        return ans;
    }
};

形成3的最大倍数

  • 题面:

第4题

  • 思路:老题了,先按照字符大小从大到小排序,然后看一下所有数字求和(记作sum)模上3等于多少,分情况讨论即可。
    • 如果sum=0,那么所有数字都可以,直接返回排序后的字符串。
    • 如果sum=1,要么直接删除一个最小(从后往前遍历)的模上3等于1的(记住这里就可以直接return了,我脑子晕了会,wa了5发,差点前200都保不住),要么删除2个模上3等于2的数。否则无解。
    • 如果sum=2,要么直接删除一个最小(从后往前遍历)的模上3等于2的(记住这里就可以直接return了),要么删除2个模上3等于1的数。否则无解。
  • 复杂度:O(n)
  • 代码(写得很丑。。):
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        sort(digits.begin(), digits.end(), greater<int>{});
        int sum = 0;
        int len = digits.size();
        for(int i=0; i<len; i++){
            sum += digits[i]%3;
        }
        sum %= 3;
        string ans="";
        if(sum==0){
            for(int i=0; i<len; i++){
                ans += digits[i]+'0';
            }
        }
        else if(sum==1){
            int pos = -1;
            for(int i=len-1; i>=0; i--){
                if(digits[i]%3==1){
                    pos=i;
                    break;
                }
            }
            if(pos != -1){
                    for(int i=0; i<len; i++){
                    if(i==pos) continue;
                    ans += digits[i]+'0';
                }
                return ans;
            }
            int pos1 = -1, pos2 = -1;
            for(int i=len-1; i>=0; i--){
                if(digits[i]%3==2 && pos1==-1){
                    pos1 = i;
                }
                else if(digits[i]%3==2 && pos2==-1){
                    pos2 = i;
                }
                else if(pos1>0&&pos2>0){
                    break;
                }
            }
            if(pos1!=-1&&pos2!=-1){
                for(int i=0; i<len; i++){
                    if(i==pos1||i==pos2) continue;
                    ans += digits[i]+'0';
                }
            }
        }
        else{
            int pos = -1;
            for(int i=len-1; i>=0; i--){
                if(digits[i]%3==2){
                    pos=i;
                    break;
                }
            }
            if(pos != -1){
                    for(int i=0; i<len; i++){
                    if(i==pos) continue;
                    ans += digits[i]+'0';
                }
                return ans;
            }
            int pos1 = -1, pos2 = -1;
            for(int i=len-1; i>=0; i--){
                if(digits[i]%3==1 && pos1==-1){
                    pos1 = i;
                }
                else if(digits[i]%3==1 && pos2==-1){
                    pos2 = i;
                }
                else if(pos1>0&&pos2>0){
                    break;
                }
            }
            if(pos1!=-1&&pos2!=-1){
                for(int i=0; i<len; i++){
                    if(i==pos1||i==pos2) continue;
                    ans += digits[i]+'0';
                }
            }
        }
        if(ans=="") return ans;
        string ans2 = "";
        int p = -1;
        for(int i=0; i<ans.size(); i++){
            if(ans[i]!='0'){
                p=i;
                break;
            }
        }
        if(p==-1) ans2="0";
        else{
            for(int i=p; i<ans.size(); i++){
                ans2+=ans[i];
            }
        }
        return ans2;
    }

};

本文分享自微信公众号 - GiantPandaCV(BBuf233),作者:BBuf

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 第 167 场周赛题解

    BBuf
  • LeetCode 221场周赛题解

    【GiantPandaCV导语】这是LeetCode的第221场周赛的题解,本期考察的知识点有模拟,贪心,优先队列,01Trie树等。

    BBuf
  • LeetCode第166场周赛题解

    这是LeetCode的第166场周赛的题解,不出意外的又爆炸了,前三题只做了20分钟,第4题因为题意读错了耽误了40分钟,到1小时15分钟左右才写完。排名直接1...

    BBuf
  • 【hdu 4658】Integer Partition (无序分拆数、五边形数定理)

    饶文津
  • 树链剖分简单分析及模板(杂谈)

    这几天学习了一下树链剖分,顺便写一下我的理解、 早上看了一下别人的讲解,云里雾里,终于算是搞懂了、 树链剖分是解决在树上进行插点问线,插线问点等一系列树上的问题...

    Angel_Kitty
  • 201403-1

    试题编号: 201403-1 试题名称: 相反数 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述 ...

    小二哥
  • 指针*和引用&的区别使用

    首先,&不是地址运算符,而是类型标识符的一种,就像*也不是指针运算符一样。 本篇偏向于&运算符。

    看、未来
  • Android9.0 SystemUI 网络信号栏定制修改的流程解析

    1、新增 StatusBarMobileView 替代 SignalClusterView,用以控制信号栏显示

    砸漏
  • LintCode 接雨水题目分析方法三

    给出 n 个非负整数,代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少(面积)雨水。

    desperate633
  • CodeChef March Lunchtime 2018 div2

    地址https://www.codechef.com/LTIME58B?order=desc&sortBy=successful_submissions

    attack

扫码关注云+社区

领取腾讯云代金券