第 26 场双周赛

Posted on | In , | |
Words count in article: 406 | Reading time ≈ 2

5396. 连续字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxPower(string s) {
        if(s.size() == 0) return 0;
        char cur = s[0];
        int res = 1;
        int c = 1;
        for(int i=1; i<s.size(); i++) {
            if(s[i] == s[i-1]) c ++;
            else {
                cur = s[i]; c = 1;
            }
            res = max(res, c);
        }
        return res;
    }
};

5397. 最简分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int gcd(int a, int b) {
        if(b == 0) return a;
	    return gcd(b, a % b);
    }
    vector<string> simplifiedFractions(int n) {
        vector<string> res;
        
        for(int i=2; i<=n; i++) {
            for(int j=1; j<i; j++) {
                if(gcd(i, j) == 1) {
                    string str = to_string(j) + "/" + to_string(i);
                    res.push_back(str);
                }
            }
        }
        
        return res;
    }
};

5398. 统计二叉树中好节点的数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    void dfs(TreeNode* root, int curmax) {
        if(root == NULL) return;
        if(root->val >= curmax) ans++;
        curmax = max(curmax, root->val);
        dfs(root->left, curmax);
        dfs(root->right, curmax);
    }
    int goodNodes(TreeNode* root) {
        dfs(root, INT_MIN);
        return ans;
    }
};

5399. 数位成本和为目标值的最大数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    string null="null";
    vector<int>v;
    map<int,string>m;
    bool cmp(string s1,string s2){
        if(s1.size()==s2.size())return s1>s2;
        return s1.size()>s2.size();
    }
    string dfs(int target){
        if(target==0)return ""; 
        if(m.count(target))return m[target];
        string answ="";
        for(int i=0;i!=v.size();i++){
            if(target>=v[i]){
                string ans=dfs(target-v[i]);
                if(ans!=null&&cmp(to_string(i+1)+ans,answ))answ=to_string(i+1)+ans;
            }
        }
        return m[target]=answ.empty()?null:answ;
    }
    string largestNumber(vector<int>& cost, int target) {
        v=cost;
        return dfs(target)==null?"0":dfs(target);
    }
};
Donate? comment?