首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode Contest 177

LeetCode Contest 177

作者头像
ShenduCC
发布2020-02-25 15:01:06
2610
发布2020-02-25 15:01:06
举报
文章被收录于专栏:算法修养算法修养

Number of Days Between Two Dates

计算两个日期的相差天数

public class Solution {
    public int DaysBetweenDates(string date1, string date2) {
        
        DateTime time1 = DateTime.Parse(date1);
        DateTime time2 = DateTime.Parse(date2);
        
        return Math.Abs((time2-time1).Days);
        
    }
}

Validate Binary Tree Nodes

给你一些点和边,判断是否是一颗二叉树。只需要判断所有点的入度<=1 ,并且入度为0的点只有一个,就可以了。

class Solution {
public:
    int b[10005];
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        
        for(int i=0;i<n;i++)
        {
            if(leftChild[i]!=-1)
            {
                b[leftChild[i]]++;
                if(b[leftChild[i]]>1)
                    return false;
            }
        }
        
        for(int i=0;i<n;i++)
        {
            if(rightChild[i]!=-1)
            {
                b[rightChild[i]]++;
                if(b[rightChild[i]]>1)
                    return false;
            }
        }
        
        int pos =0;
        int num=0;
        for(int i=0;i<n;i++)
        {
            if(b[i]==0)
            {
                pos=i;
                num++;
            }
        }
        
        if(num!=1)
            return false;
        
       return true;
        
    }
};

Closest Divisors

从sqrt(x)往前找就可以了,找到的第一个一定是最优的。

class Solution {
public:
    vector<int> closestDivisors(int num) {
        
        vector<int> ans;
        vector<int> ans2;
        if(fun(num+1,ans) <= fun(num+2,ans2)) return ans;
        return ans2;
    }
    
    int fun(int x,vector<int>& res)
    {
        int i = (int)sqrt(x);
        
        for(;i>=1;i--)
        {
            if(x%i==0)
            {
                res.push_back(i);res.push_back(x/i);
                return abs(i-x/i);
            }    
        }
        return INT_MAX;
    }
};

Largest Multiple of Three

被三整除的数,每个数位上的数字之和能被3整除。 也就是在这个数列里找到一个子数列,之和能被3整除,并且这个数列长度是最长的,最后按照数列的倒序输出成字符串。

我们把数列里的数字分成三种,c[]被3整除的,b[]被3除余1的,a[]被三除余2的,倒序排序,越大的数字越优先。

答案中肯定包含所有c[]里的数字,其次就是b[]和a[]的组合。 一个b和a的和可以被三整除,3个b和3个a也可以分别被三整除。

关键就是怎么可以从a和b中拿出最多的数字。

思路就是首先,两个数组的长度都大于等于3的话,那么从第一个元素开始,每三个元素都是一定会被选中的。直到剩下的元素不足三个。而且两个数组必须同时满足剩下的元素大于3个这个条件。

经过第一次筛选之后,剩下的分情况讨论。假设剩下的元素多的个数为x,剩下元素个数少的个数为y,其中0<=y<=2,x>y 如果 x>3 把x数组里的元素组合起来,最后剩余的是x=x%3

x=3,y=2 选择把x,y搭配 x=3,y=1 把x元素组合起来 x<3 选择把x,y搭配 y==0 只选择x

class Solution {
public:
    vector<int> a;
    vector<int> b;
    vector<int> c;
    vector<int> d;
    string largestMultipleOfThree(vector<int>& digits) {
        
        for(int i=0;i<digits.size();i++)
        {
            if(digits[i]%3==0)
                c.push_back(digits[i]);
            if(digits[i]%3==2)
                a.push_back(digits[i]);
            if(digits[i]%3==1)
                b.push_back(digits[i]);
        }
        
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        
        int i,j;
        i=a.size()-1;
        j=b.size()-1;
        
        for(;i>=2&&j>=2;i-=3,j-=3)
        {
            d.push_back(a[i]);
            d.push_back(a[i-1]);
            d.push_back(a[i-2]);
            d.push_back(b[j]);
            d.push_back(b[j-1]);
            d.push_back(b[j-2]);
        }
        
        if(i<j)
            fun(b,a,j,i);
        else
            fun(a,b,i,j);
       
        
        i=0;
        for(;i<c.size();i++)
        {
            d.push_back(c[i]);
        }
        
        sort(d.begin(),d.end());
        
        string ans="";
        
        i=d.size()-1;
        for(;i>=0;i--)
        {
            ans+='0'+d[i];
        }
        
        if(ans[0]=='0'&&ans[ans.length()-1]=='0')
            ans="0";
        
        return ans;
        
    }
    
    void fun(vector<int>& nums1,vector<int>& nums2,int i,int j)
    {
        if(j==-1)
        {
            for(;i>=2;i-=3)
            {
                d.push_back(nums1[i]);
                d.push_back(nums1[i-1]);
                d.push_back(nums1[i-2]);
            }
        }

        for(;i>2;i-=3)
        {
            d.push_back(nums1[i]);
            d.push_back(nums1[i-1]);
            d.push_back(nums1[i-2]);
        }
        
        if(j==0&&i==2)
        {
            d.push_back(nums1[i]);
            d.push_back(nums1[i-1]);
            d.push_back(nums1[i-2]);
            
        }
        else
        {
       
            for(;i>=0&&j>=0;j--,i--)
            {
                d.push_back(nums1[i]);
                d.push_back(nums2[j]);
            }
        }
        
    }
 
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-02-23 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档