©2020-2024 ioDraw All rights reserved,
Privacy Policy
在庆祝祖国母亲70华诞之际，老师给小乐乐出了一个问题。大家都知道China的英文缩写是CHN，那么给你一个字符串s，你需要做的是统计s中子串“CHN”的个数。
子串的定义：存在任意下标a < b <
c，那么“s[a]s[b]s[c]”就构成s的一个子串。如“ABC”的子串有“A”、“B”、“C”、“AB”、“AC”、“BC”、“ABC”。
输入描述：
输入只包含大写字母的字符串s。(1 ≤ length ≤ 8000)
输出描述：
输出一个整数，为字符串s中字串“CHN”的数量。
示例1
输入：
CCHNCHN
输出：
7
第一种方法算法复杂度高，遍历全部的可能性；
int main() { char arr[8001] = { 0 }; scanf("%s", arr); int st = 0; int u = 0;
while (arr[u] != 0) { st++; u++; } st = st +1; int i = 0; int j = 0; int k = 0;
int count = 0; for (i = 0; i < st - 1; i++) { if (arr[i] == 'C') { for (j = i +
1; j < st - 1; j++) { if (arr[j] == 'H') { for (k = j + 1; k < st - 1; k++) { if
(arr[k] == 'N') { count++; } } } } } } printf("%d", count); return 0; }
方法二
可以先找C的子序列，那么遇到H的话就组成CH此时有C个"CH”序列
也就是说ch的个数取决于c的个数，同理，当你找到“N”的时候,就是“CH“还有"N组成的“CHN”，"CH“的个数就是“CHN”的个数，把个数做累加。
#include<stdio.h> #include<string.h> int main() { char str[8000]; scanf("%s\n",
str);//CCHNCHN char* ps = str; long long c = 0, ch = 0, chn = 0; while (*ps) {
if (*ps == 'C') { c++; } else if (*ps == 'H') { ch += c; } else if (*ps == 'N')
{ chn += ch; } ps++; } printf("%lld\n", chn); return 0; }