letcode第 311 场周赛_311场周赛csdn

6180. 最小偶倍数

略

class Solution {
public:
    int smallestEvenMultiple(int n) {
        if(n&1)return n*2;
        return n;
    }
};

6181. 最长的字母序连续子字符串的长度

最长也就26，枚举即可

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int n=s.length();
        for(int len=26;len>=1;len--){
            for(int l=0;l+len-1<n;l++){
                int r=l+len-1;
                bool flag = true;
                for(int k=l+1;k<=r;k++){
                    if(s[k]!=s[k-1]+1){
                        flag=false;
                    }
                }
                if(flag){
                    return len;
                }
                
            }
        }
        return 1;
    }
};

6182. 反转二叉树的奇数层

记录奇数层即可

/**
 * 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:
    vector<int>v[100007];
    int id[100007];
    void dfs(TreeNode* tmp, int dep){
        if(dep&1){
            v[dep].push_back(tmp->val);
        }
        if(tmp->left){
            dfs(tmp->left,dep+1);
            dfs(tmp->right,dep+1);
        }
    }
    void gao(TreeNode* tmp, int dep){
        if(dep&1){
            tmp->val=v[dep][v[dep].size()-id[dep]-1];
            id[dep]++;
        }
        if(tmp->left){
            gao(tmp->left,dep+1);
            gao(tmp->right,dep+1);
        }
    }
    TreeNode* reverseOddLevels(TreeNode* root) {
        memset(id,0,sizeof(id));
        dfs(root,0);
        gao(root,0);
        return root;
    }
};

6183. 字符串的前缀分数和

显然，分数即每个串与其他所有串的LCP之和。

按字典序排序后，类似滑动窗口做就行。

或者直接字典树。

class Solution {
public:
    
    int id[1007],lcp[1007];
    vector<int> sumPrefixScores(vector<string>& words) {
        vector<pair<string, int> >x;
        for(int i=0;i<words.size();i++){
            x.push_back({words[i],i});
        }
        sort(x.begin(),x.end());
        int n = x.size();
        for(int i=1;i<n;i++){
            int len=0;
            while(len<words[x[i].second].length() && len<words[x[i-1].second].length() && words[x[i].second][len]==words[x[i-1].second][len])len++;
            lcp[i]=len;
        }
        lcp[0]=1111;
        vector<int>ANS;
        for(int i=0;i<n;i++)ANS.push_back(0);
        for(int i=0;i<n;i++){
            int ans=0;
            int id=0;
            for(int j=0;j<n;j++){
                int a=x[i].second,b=x[j].second;
                id=min(id,lcp[j]);
                while((id>words[a].length()) || (id>words[b].length()))id--;
                while((id<words[a].length())&& (id<words[b].length()) && (words[a][id]==words[b][id])){
                    id++;
                }
                while((id-1>=0) && (words[a][id-1]!=words[b][id-1])){
                    id--;
                }
                ans+=id;
            }   
            ANS[x[i].second]=ans;
        }
        return ANS;
    }
};