38-Count And Say
程序员文章站
2022-07-15 12:06:17
...
类别:string
题目描述
算法分析
1:“1”(有1个1)
2:“11”(表示上一个即第一个有1个1,而当前有2个1)
3:“21”(表示上一个即第二个有2个1,而当前有1个2,1个1)
3:“1211”(表示上一个即第三个有1个2和1个1,而当前有1个1,1个2,2个1)
4:“111221”……
给定数字n,需要从第一个数推到n,初始化strs[1] = “1”,然后用一个循环计算之后的每一个序号对应的字符串,对于每一个序号对应的字符串,需要用其前面一个字符串进行计算,遍历字符串,并且计算每一个数字出现的次数然后转换为字符串即可。
代码实现
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string countAndSay(int n) {
vector<string> readStr;
readStr.push_back("1");
string str = "", generateStr = "";
int n1 = 0, count = 0;
char pre = ' ';
for (int i = 1; i < n; ++i) {
generateStr = "";
str = readStr[i - 1];
n1 = str.length();
count = 1;
pre = str[0];
for (int j = 1; j < n1; ++j) {
// count the continous same char
if (str[j] == pre) {
count++;
} else {
// add chars
generateStr += count + '0';
generateStr += pre;
count = 1;
pre = str[j];
}
}
// add last chars
generateStr += count + '0';
generateStr += pre;
readStr.push_back(generateStr);
}
return readStr[n - 1];
}
int main() {
int n;
cin >> n;
cout << countAndSay(n) << endl;
return 0;
}
上一篇: 89.格雷编码