HNU软件能力实训3-8. ab串

写在前面

你好!欢迎来到我的博客,希望我的思路能够帮到你!

问题描述

给定一个由字符’a’和字符’b’组成的字符串,可以删除若干字符,使得剩下来的字符串满足前后段为a,中间段为b(aaa…aaabbbb…bbbbaaa…aaa),区段可以没有字符(ba,ab,b,aa都是合法的),求最长剩下字符串的长度。

输入形式

输入为一行一个长度不超过5000的非空字符串,字符串仅由字符’a’和字符’b’组成。

输出形式

输出为一个整数,表示符合要求的最长剩下字符串长度

样例输入

【样例输入1】

abba

【样例输入2】

bab

样例输出

【样例输出1】

4

【样例输出2】

2

解题思路

这道题又是一个新的知识点——前缀和。

大致思路是这样的:我们用 numa[ i ]numb[ i ] 分别记录位置 i 之前的 a 的个数和 b 的个数,然后以 ij 作为双指针,( j <= i ) 来遍历所有的可能,寻找出一个最大的长度。

然后代码这一句:
int MAX=max(mp[‘b’]?mp[‘a’]+1:mp[‘a’],mp[‘b’]);
小可爱们可能看不懂,这里其实是一个特判,由于最长可能有这两种特殊情况:

1、中间一个b,两边是所有的a。
2、没有a,全部都是b。
mp[‘b’]?mp[‘a’]+1:mp[‘a’] 对应的是中间一个b,两边是所有的a。
mp[‘b’] 对应的是没有a,全部都是b。

相信现在小可爱们看懂这段代码不是问题。

AC代码

#include<iostream>
#include<map>
#include<string>
#include<algorithm>

using namespace std;
const int N=5010;

int numa[N],numb[N];
//num1表示a的前缀和,num2表示b的前缀和

int main()
{
    string s;
    cin>>s;
    map<char,int> mp;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='a'&&i==0) numa[i]=1;
        else if(s[i]=='b'&&i==0) numb[i]=1;//对第一位进行特判
        else if(s[i]=='a')//这里是构建前缀和
        {
            numa[i]=numa[i-1]+1;
            numb[i]=numb[i-1];
        }
        else if(s[i]=='b')
        {
            numb[i]=numb[i-1]+1;
            numa[i]=numa[i-1];
        }
        mp[s[i]]++;//存储ab对应的个数
    }
    int MAX=max(mp['b']?mp['a']+1:mp['a'],mp['b']);//这一段在上面有解释
    //int MAX=-1;
    //经过后续测试,上面一句简单的也行...
    for(int i=0;i<s.size();i++)
    {
        for(int j=0;j<i;j++)
        {
            int ans1=numa[j];//这里是第一段a的个数
            int ans2=numb[i]-numb[j-1];//这里是中间段b的个数
            int ans3=numa[s.size()-1]-numa[i-1];//这里是后面一段a的个数
            int ans=ans1+ans2+ans3;
            if(ans>MAX) MAX=ans;//更新最大值
        }
    }
    printf("%d\n",MAX);
    system("pause");
    return 0;
}

写在最后

如果代码有任何问题,欢迎评论或者私信斧正。如果内容对对你有启发,不妨点个赞吧

上一篇:挑战Redis单实例内存最大极限,“遭遇”NUMA陷阱!


下一篇:C语言:随机抽奖