第 21 场双周赛

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

1370. 上升下降字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string sortString(string s) {
        vector<int> tmp(26);
        for(int i=0; i<s.size(); i++) tmp[s[i]-'a'] ++;
        string ret;
        while(ret.size() < s.size()) {
            for(int i=0; i<26; i++) if(tmp[i]) ret+=i+'a', tmp[i]--;
            for(int i=25; i>=0; i--) if(tmp[i]) ret+=i+'a',tmp[i]--;
        }
        return ret;
    }
};

1371. 每个元音包含偶数次的最长子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findTheLongestSubstring(string s) {
        string v = "aeiou";
        int state = 0;
        int maxSize = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for(int i=0; i<s.size(); i++) {
            for(int k=0; k<5; k++) {
                if(v[k] == s[i]) {
                    state ^= (1 << k);
                    break;
                }
            }
            if(mp.find(state) != mp.end()) {
                maxSize = max(maxSize, i-mp[state]);
            } else {
                mp[state] = i;
            }
        }
        return maxSize;
    }
};

1372. 二叉树中的最长交错路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int ans=0;
    void dfs(TreeNode* root,int dir,int dis){//(当前结点，左/右孩子，路径长度)
        if(!root)return;
        ans=max(ans,dis);
        if(dir){//如果当前结点是其父结点的右孩子
            dfs(root->left,0,dis+1);//搜索其左孩子时，满足ZigZig，路径长度+1
            dfs(root->right,1,1);//搜索其右孩子时，不满足ZigZig，路径长度置为1
        } 
        else{//如果当前结点是其父结点的左孩子
            dfs(root->left,0,1);//搜索其左孩子时，不满足ZigZig，路径长度置为1
            dfs(root->right,1,dis+1);//搜索其右孩子时，满足ZigZig，路径长度+1
        }       
    }
public:
    int longestZigZag(TreeNode* root) {
        dfs(root->left,0,1);
        dfs(root->right,1,1);
        return ans;
    }
};

1373. 二叉搜索子树的最大键值和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxsum = 0;
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return maxsum;
    }
    vector<int> dfs(TreeNode* root) {
        if (!root) return {true, INT_MAX, INT_MIN, 0};
        auto lArr = dfs(root->left);
        auto rArr = dfs(root->right);
        int sum = 0, curmax, curmin;
        if (!lArr[0] || !rArr[0] || root->val >= rArr[1] || root->val <= lArr[2]) {
            return {false, 0, 0, 0};
        }
        curmin = root->left ? lArr[1] : root->val;
        curmax = root->right ? rArr[2] : root->val;
        sum += (root->val + lArr[3] + rArr[3]);
        maxsum = max(maxsum, sum);
        return {true, curmin, curmax, sum};
    }
};
Donate? comment?