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^4，leftChild.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;
    }

};