前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >力扣 第 177 场周赛 题解

力扣 第 177 场周赛 题解

作者头像
BBuf
发布2020-02-26 15:47:01
3790
发布2020-02-26 15:47:01
举报
文章被收录于专栏:GiantPandaCV

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

在这里插入图片描述

日期之间隔几天

  • 题面:

第一题

  • 思路:主要是考虑一下闰年和平年,以及每个月有多少天,简单的模拟题。
  • 代码:
代码语言:javascript
复制
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)
  • 代码:
代码语言:javascript
复制
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))
  • 代码:
代码语言:javascript
复制
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)
  • 代码(写得很丑。。):
代码语言:javascript
复制
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;
    }

};
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 GiantPandaCV 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 日期之间隔几天
  • 验证二叉树
  • 最接近的因数
  • 形成3的最大倍数
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档