Rank: 1753 / 4033 AC: 1/4 Score: 3/18

5543. 两个相同字符之间的最长子字符串

枚举每个字符，然后在字符串中查找第一次和最后一次的位置，然后更新res
时间复杂度：

class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        int res = -1;
        for(char c = 'a';c<='z';c++){
            int l = s.size(), r = 0;
            for(int i=0;i<s.size();i++){
                if(s[i]==c){
                    l = min(l,i);
                    r = max(r,i);
                }
            }
            res = max(res,r-l-1);
        }
        return res;
    }
};

5544. 执行操作后字典序最小的字符串

思维题
首先题目保证字符串长度为偶数，一般来讲加法操作只需要枚举10次就可以，，对于旋转操作只需要枚举n次就可以，因为n次就变回了原串。
下面分情况讨论：

• b是偶数，则奇数位集合不变，因此操作顺序不影响结果，时间复杂度 其中比较字符串字典序时间复杂度为
• b是奇数，则奇数位和偶数位都可以加a，但是依旧不影响答案，答案主要受奇数位操作次数、偶数位操作次数和向后移动多少次等，时间复杂度

  class Solution {
  public:
    void update(char &c,int a){
        c = (c-'0'+a)%10+'0';
    }
    string findLexSmallestString(string s, int a, int b) {
        int n = s.length();
        string res = s;
        if(b%2==0){
            for(int i=0;i<10;i++){  // 枚举奇数位加法次数
                for(int j=1;j<n;j+=2) update(s[j],a);
                string t = s;
                for(int k=0;k<n;k++){  // 枚举n次旋转
                    t = t.substr(n-b)+t.substr(0,n-b);
                    res = min(res,t);
                }
            }
            return res;
        }
        else {
            for(int i=0;i<10;i++){  // 枚举奇数位加法次数
                for(int j=1;j<n;j+=2) update(s[j],a); // 奇数位加法
                for(int j=0;j<10;j++){  // 枚举偶数位加法次数
                    for(int k=0;k<n;k+=2) update(s[k],a);  // 偶数位加法
                    string t = s;
                     // 枚举n次旋转 
                    for(int k=0;k<n;k++) {
                        t = t.substr(n-b)+t.substr(0,n-b);
                        res = min(res,t);
                    }
                }
            }
            return res;
        }
        return res;
    }
  };
  

  5545. 无矛盾的最佳球队

  最大上升子序列和的问题，时间复杂度：

  class Solution {
  public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n  = ages.size();
        vector<pair<int,int>> q(n);
        for(int i=0;i<n;i++) {
            // 第一关键字为年龄，第二关键字为分数
            q[i] = make_pair(ages[i],scores[i]);
        }
        // 按照年龄升序排序，如果年龄相同按照分数升序排序
        sort(q.begin(),q.end());
        int res = 0;
        // dp数组,表示以i为结尾的序列得到的最佳得分
        vector<int> f(n);
        for(int i=0;i<n;i++){
            f[i] = q[i].second;
            for(int j=0;j<i;j++){
                // 如果在i前面的j球员（i年龄比j大），j的水平比i高
                if(q[i].second>=q[j].second){
                    // 状态更新呢
                    f[i] = max(f[i],f[j]+q[i].second);
                }
            }
            // 从以i结尾的序列中得到的结果中取最大值
            res = max(res,f[i]);
        }
        return res;
    }
  };
  

  5128. 带阈值的图连通性

  图论和数论结合的题目，很明显是一个并查集的题目，如果通过求解1-n之间的数的最大公约数，很明显是的时间复杂度会超时，现在逆向思维，题目保证公约数要大于t，所以我们从d=t+1到d=n进行建图，d,2d,3d,…kd会并在一起，最后再进行查询。时间复杂度为，考虑到并查集的查询的复杂度为,因此总的时间复杂度为

  class Solution {
  public:
    vector<int> p;
    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    void Union(int a,int b){
        int fa = find(a), fb = find(b);
        if(fa<=fb) p[fb] = fa;
        else p[fa] = fb;
    }
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        p.resize(n+1);
        for(int i=1;i<=n;i++) p[i] = i;
        vector<bool> res;
        for(int d=threshold+1;d<=n;d++){
            for(int i=d*2;i<=n;i+=d){
                Union(i,d);
            }
        }
        for(auto&e:queries){
            res.push_back(find(e[0])==find(e[1]));
        }
        return res;
    }
  };