【Leetcode】第4场双周赛

1118. 一月有多少天

指定年份 $Y$Y 和月份 $M$M，请你帮忙计算出该月一共有多少天。

示例 $1$1：

输入：Y = 1992,M = 7
输出：31

示例 $2$2：

输入：Y = 2000, M = 2
输出：29

示例 $3$3：

输入：Y = 1900, M = 2
输出：28

解：判断是否为闰年，输入月份对应的天数即可

class Solution {
public:
    int day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 
    int numberOfDays(int Y, int M) {
        if (Y % 400 == 0 || (Y % 4 == 0 && Y % 100 != 0)) {
            day[2]++;
        }
        return day[M];
    }
};

1119. 删去字符串中的元音

给你一个字符串 $S$S，请你删去其中的所有元音字母（ $'a'，'e'，'i'，'o'，'u'$′a′，′e′，′i′，′o′，′u′），并返回这个新字符串。

示例 $1$1：

输入："leetcodeisacommunityforcoders"
输出："ltcdscmmntyfrcdrs"

示例 $2$2：

输入："aeiou"
输出：""

提示：

S 仅由小写英文字母组成。
1 <= S.length <= 1000

解：新建一个字符串，判断如果是元音则不加入新字符串，否则加入

class Solution {
public:
    string removeVowels(string S) {
        string str = "";
        for (int i = 0; i < S.size(); ++i) {
            if (S[i] == 'a' || S[i] == 'e' || S[i] == 'i' || S[i] == 'o' || S[i] == 'u') 
                continue;
            str += S[i];
        }
        return str;
    }
};

1120. 子树的最大平均值

给你一棵二叉树的根节点 $root$root，找出这棵树的 每一棵 子树的 平均值 中的 最大 值。

子树是树中的任意节点和它的所有后代构成的集合。

树的平均值是树中节点值的总和除以节点数。

示例：

输入：[5,6,1]
输出：6.00000
解释： 
以 value = 5 的节点作为子树的根节点，得到的平均值为 (5 + 6 + 1) / 3 = 4。
以 value = 6 的节点作为子树的根节点，得到的平均值为 6 / 1 = 6。
以 value = 1 的节点作为子树的根节点，得到的平均值为 1 / 1 = 1。
所以答案取最大值 6。

提示：

树中的节点数介于 1 到 5000之间。
每个节点的值介于 0 到 100000 之间。
如果结果与标准答案的误差不超过 10^-5，那么该结果将被视为正确答案。

解：定义一个$solve$solve函数求解以当前节点为子树根节点形成的$val$val(节点值之和)以及$len$len(节点个数)；遍历每个节点得到平均值$(double)val / len$(double)val/len，每次更新该平均值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    double ans = 0;
    void solve(TreeNode* root, int &val, int &len) {
        if (root == nullptr) 
            return ;
        else {
            val += root->val;
            len += 1;
        }
        solve(root->left, val, len);
        solve(root->right, val, len);
    }
    double maximumAverageSubtree(TreeNode* root) {
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* cur = st.top();
            st.pop();
            int val = 0, len = 0;
            solve(cur, val, len);
            //cout << val << " " << len << " ";
            double t = (double)val / len;
            if (t > ans)
                ans = t;
            //cout << t << " " << endl;
            if (cur->left) st.push(cur->left);
            if (cur->right) st.push(cur->right);
        }
        return ans;
    }
};

1121. 将数组分成几个递增序列

给你一个 非递减 的正整数数组 $nums$nums 和整数 $K$K，判断该数组是否可以被分成一个或几个 长度至少 为 $K$K 的 不相交的递增子序列。

示例 $1$1：

输入：nums = [1,2,2,3,3,4,4], K = 3
输出：true
解释：
该数组可以分成两个子序列 [1,2,3,4] 和 [2,3,4]，每个子序列的长度都至少是 3。

示例 $2$2：

输入：nums = [5,6,6,7,8], K = 3
输出：false
解释：
没有办法根据条件来划分数组。

提示：

1 <= nums.length <= 10^5
1 <= K <= nums.length
1 <= nums[i] <= 10^5

解：首先对$nums$nums排个序，得到一个递增数组；(1)当$n$n小于$K$K，即一个递增子序列也不能形成，那么直接返回$false$false；(2)当$n$n大于等于$K$K，即可形成一个或多个递增子序列，那么只需要判断$nums$nums数组中每个元素出现的次数是否大于$K$K就行了，如果大于$K$K则必定形成的某个子序列中含有重复值，否则成立

class Solution {
public:
    bool canDivideIntoSubsequences(vector<int>& nums, int K) {
        int n = nums.size();
        if (n < K) 
            return false;
        sort(nums.begin(), nums.end());
        int m = n / K;
        map<int, int> mp;
        for (int i = 0; i < n; ++i){
            mp[nums[i]]++;
        }
        for (auto it : mp) {
            if (it.second > m)
                return false;
        }
        return true;
    }
};