题目描述
在庆祝祖国母亲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”的数量。
我的解答
最基本的思路，就是时间复杂度太高O(n^3)
自测能过，但OJ提示时间过长超时，算法复杂度高
# include<bits/stdc++.h> using namespace std; int main() { string s; int count = 0; cin>>s; char ch[s.length()]; for(int i = 0;i<s.length();i++){ ch[i] = s.at(i); } for(int j = 0;j<s.length();j++){ if(ch[j] == 'C'){ for(int k = j + 1;k<s.length();k++){ if(ch[k] == 'H'){ for(int m = k + 1;m<s.length();m++){ if(ch[m] == 'N') count ++; } } } } } cout<<count<<endl; return 0; } 题解思路：
可以先找C的子序列，那么遇到H的话就组成CH此时有C个"CH”序列，同理，当你找到“N”的时候,就是“CH“还有"N组成的“CHN”，"CH“的个数就是“CHN”的个数，把个数做累加。
#include<iostream> using namespace std; int main() { ios::sync_with_stdio(0);//而这段语句可以来打消iostream的输入 输出缓存，可以节省许多时间 string s; cin >> s;//输入s long long ans = 0;//初始化为0 long long sum = 0;//初始化为0 int c=0, h=0;//初始化为0 int u; for (int i = 0; i < s.size(); i++)//s.size()，字符串s的长度 { if (s[i] == 'C')//如果第一个符合C { c++; } else if (s[i] == 'H')//遇到H的话就组成CH此时有C个"CH”序列 { h += c; } else if(s[i]=='N')//找到“N”的时候,就是“CH“还有"N组成的“CHN” { ans +=h;//个数做累加 } } cout << ans << endl;//输出结果 return 0; } # include<bits/stdc++.h> using namespace std; int main() { string s; cin>>s; char ch[s.length()]; //注意，这里使用int部分通过 long long c = 0,c_h = 0,c_h_n = 0; for(int i = 0;i<s.length();i++){ ch[i] = s.at(i); } for(int j = 0;j<s.length();j++){ if(ch[j] == 'C'){ c ++; } else if(ch[j] == 'H'){ c_h += c; } else if(ch[j] == 'N'){ c_h_n += c_h; } } cout<<c_h_n<<endl; return 0; }