青岛市城市建设局网站,静态网站模板下载,优化大师最新版本,郑州 网站建设 东区题目描述#xff1a; leafee 最近爱上了 abb 型语句#xff0c;比如“叠词词”、“恶心心”。 leafee 拿到了一个只含有小写字母的字符串#xff0c;她想知道有多少个 abb 型的子序列#xff1f;
定义#xff1a; abb 型字符串满足以下条件#xff1a; 字符…题目描述 leafee 最近爱上了 abb 型语句比如“叠词词”、“恶心心”。 leafee 拿到了一个只含有小写字母的字符串她想知道有多少个 abb 型的子序列
定义 abb 型字符串满足以下条件 字符串长度为 3 。 字符串后两位相同。 字符串前两位不同。
输入描述: 第一行一个正整数 n 第二行一个长度为 n 的字符串只包含小写字母(1≤n≤10^5)
输出描述:
abb 型的子序列个数。 示例1
输入:
6
abcbcc
输出:
8
说明: 共有1个abb3个acc4个bcc 示例2
输入:
4
abbb
输出:
3
解题思路 本题是求字符串中所以的abb序列我们采用的方法是先将字符串中的所有字符的个数记录下来分别存储在char_number数组的对应位置例如字符a的个数存储在char_number[0]的位置。然后依次遍历整个字符串找到该字符后面所有字符的个数char_number当某个字符与该字符不同且其个数2那么就会产生以该字符为首的abb序列其个数为然后再将该字符所对应的char_number数-1代表后面该字符的个数-1最终循环结束过后就可以得到所以的序列个数。
注意 ①当字符串长度过大时可能会导致最终计算得到的序列个数较大所以不能采用int型来记录序列个数可以采用long long型来记录序列个数 ②本题的问题是求得字符串中所有的序列而不是连续的序列abb ③采用3个循环得到的运行会超时所以最多只能采用两个循环。
代码
#includeiostream
using namespace std;
int main()
{//创建一维动态数组int num; //用于存储字符的个数cinnum;char *ch new char[num];//输入字符for(int i0;inum;i){cinch[i];}//查找long long total 0; //用于记录abb型序列的个数int char_number[27] {0};//记录每个字符的个数for(int i0;inum;i){//将每个字符对应的数组下标i所对应的值1,例如a对应数组下标0若ch[j]a,则char_number[0]char_number[ch[i]-97];} //若j后面含有n个相同的字符则会构成n-1个abb序列其中n1for(int j0;jnum-2;j){for(int k0;k26;k){if(char_number[k] 1 k ! int(ch[j]-97)){total char_number[k] * (char_number[k]-1) / 2;}}//将这个字符在数组中的个数-1用于记录在这个字符后面的各个字符个数char_number[int(ch[j]-97)]--;}couttotalendl;system(pause);return 0;
}
