bran's Blog
0%

leetcode周赛-211

发表于 分类于

这场睡过头了没有打，补一下

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

签到题还Wa了一发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxLengthBetweenEqualCharacters(string s) {
        unordered_map<char,int> mp;
        int ans=-1;
        for(int i=0;i<s.length();i++){
            if(mp.count(s[i])>0){
                ans=max(ans,i-mp[s[i]]-1);
            }
            else mp[s[i]]=i;
        }
        return ans;
    }
};

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

注意到所有奇数位同步变化，所有偶数位同步变化，所以可以直接枚举最终状态。

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
27
class Solution {
public:
    int gcd(int a,int b){
        return b==0?a:gcd(b,a%b);
    }
    string findLexSmallestString(string s, int a, int b) {
        int n=s.length();
        int g=gcd(n,b);
        vector<string>vec;
        string s2=s+s;
        for(int i=0;i<n;i+=g){
            vec.push_back(s2.substr(i,n));
        }
        string ans=s;
        for(int i=0;i<10;i++){
            int m=(g%2==0?1:10);//当g为偶数时，偶数位和奇数位不能互换，因此偶数位不会发生变化
            for(int j=0;j<m;j++){
                for(auto str:vec){
                    for(int k=1;k<n;k+=2)str[k]=(str[k]-'0'+i*a)%10+'0';
                    for(int k=0;k<n;k+=2)str[k]=(str[k]-'0'+j*a)%10+'0';
                    ans=min(ans,str);
                }
            }
        }
        return ans;
    }
};

C.无矛盾的最佳球队

首先对每个球员按照年龄升序排序，dp[i][j]表示在前i个人中选择了第j个人的情况下的最高得分，然后容易得到递推式和最终结果。

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
27
28
29
30
class Solution {
public:
    struct Node{
        int age,sco;
        Node(){}
        Node(int a,int s){
            age=a;sco=s;
        }
        bool operator <(const Node nd)const{
            if(age==nd.age)return sco<nd.sco;
            return age<nd.age;
        }
    };
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        vector<Node>nd;
        for(int i=0;i<scores.size();i++)nd.push_back(Node(ages[i],scores[i]));
        sort(nd.begin(),nd.end());
        vector<int>dp(nd.size(),0);
        int ans=0;
        for(int i=0;i<nd.size();i++){
            dp[i]=nd[i].sco;
            for(int j=i-1;j>=0;j--){
                if(nd[j].sco>nd[i].sco)continue;
                dp[i]=max(dp[i],dp[j]+nd[i].sco);
            }
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

D.带阈值的图连通性

直接查询会超时，用并查集预处理一下就好了（不带路径压缩还是会超时）。

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
27
28
29
30
31
32
class Solution {
public:
    vector<pair<int,int>>eg;
    vector<int>fa;
    int find(int x){
        int res=x;
        while(res!=fa[res])res=fa[res];
        return fa[x]=res;//路径压缩
    }
    vector<bool> areConnected(int n, int th, vector<vector<int>>& que) {
        vector<bool>ans;
        eg.clear();
        fa.clear();
        for(int i=th+1;i<=n/2;i++){
            for(int j=2*i;j<=n;j+=i){
                eg.push_back({i,j});
            }
        }
        fa.resize(n+1);
        for(int i=0;i<=n;i++)fa[i]=i;
        for(auto e:eg){
            int x=find(e.first),y=find(e.second);
            if(x!=y){
                fa[x]=y;
            }
        }
        for(auto q:que){
            ans.push_back(find(q[0])==find(q[1]));
        }
        return ans;
    }
};