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 的个数，然后以 i 和 j 作为双指针，( 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的个数
            //这里的numb[j-1]会越界 但是好像能过 所以我在后面再贴一段代码
            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;
}

//这里的思路仍然与上面一致 只不过下标从1开始
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5050;
char s[N];
int prea[N];
int preb[N];

int main()
{
    cin>>s+1;
    int len=strlen(s+1);
    //cout<<len<<endl;
    for(int i=1;i<=len;i++)
    {
        prea[i]=prea[i-1];
        preb[i]=preb[i-1];
        if(s[i]=='a') prea[i]++;
        else preb[i]++;
    }
    int ret=0;
    for(int i=0;i<=len;i++)
    {
        for(int j=i;j<=len;j++)
        {
            int now=(preb[i])+(prea[j]-prea[i])+(preb[len]-preb[j]);
            //preb[i] 第一段的b的个数
            //prea[j]-prea[i] 中间段的a的个数
            //preb[len]-preb[j] 后面一段的b的个数
            ret=max(ret,len-now);//更新结果
        }
    }
    cout<<ret<<endl;
    system("pause");
    return 0;
}

写在最后

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