💜一) 题目要求
描述
在庆祝祖国母亲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：暴力算法
以实例1为例，输入：CCHNCHN，输出：7
先明白为什么结果是7↓
😈给这个字符串"CCHNCHN"中每个字母从左到右依次编号1234567，那么出现"CHN"的情况：
134
137
167
234
237
267
567
思路：每找到一个C，继续向后查找H；每找到一个H，向后继续查找N
💔但是这样暴力解题用到多层循环，复杂度过大，提交不通过
#include <stdio.h> #include <string.h> int main() { char s[8000]; scanf("%s", s); int count = 0; int len = strlen(s); for (int i = 0; i < len; i++) { if (s[i] == 'C') { for (int j = i + 1; j < len; j++) { if (s[j] == 'H') { for (int ss = j + 1; ss < len; ss++) { if (s[ss] == 'N') count++; } } } } } printf("%d", count); return 0; }
法2.找规律，累加
📘因此，我们可以先找以C开头的子序列，那么遇到H的话就组成"CH"，也就是说"CH"的个数取决于C的个数，同理，当你找到“N”的时候,就是“CH“还有"N组成的“CHN”，"CH“的个数就是“CHN”的个数，把个数做累加。
#include <stdio.h> #include <string.h> int main() { char s[8000]; scanf("%s", s); int len = strlen(s); long long int count_c = 0, count_h = 0, count_n = 0; for (int i = 0; i < len; i++) { if (s[i] == 'C') count_c++; else if (s[i] == 'H') count_h += count_c; else if (s[i] == 'N') count_n += count_h; } printf("%lld", count_n); return 0; }
