标签： C++ 算法 LeetCode 字符串 递归
每日算法——leetcode系列
问题 Count and Say
Difficulty: Easy
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1is read off as"one 1"or11.
11is read off as"two 1s"or21.
21is read off as"one 2, thenone 1"or1211.
Given an integer n, generate the nth sequence.Note: The sequence of integers will be represented as a string.
class Solution {
public:
string countAndSay(int n) {
}
};
翻译
数数并报数
难度系数：容易
数数并报数顺序按如下规律开始递增：
1，11，21，1211，111221，……
1 读作“1个1”得11
11 读作“2个1”得21
21 读作“1个2、1个1”得1211
给定一个整数n，生成第n个序列。
注意：数字序列应该用字符串表示。
思路
此题我觉得英文的表面意思跟实际要的不一样。
题意：数上次字符串中的连续出现数值的个数, 将这些字符串拼接起来
- n=1时，输出字符串1；
- n=2时，因为上次字符串1，1连续出现1次，就是1个1，所以输出11；
- n=3时，由于上次字符串11，其中1连续出现两次，就是2个1，所以输出21；
- n=4时，由于上次字符串是21，其中2出现1次，1出现1次，所以输出1211；
- n=5时，由于上次字符串1211，第个1连续出现1次为11，第二个2连续出现1次为12，第三个1跟第四个1连续出现了2次，为21，所以输出111221
代码
#include <iostream>
#include <sstream>
using namespace std;
class Solution {
public:
string countAndSay(int n) {
if(n == 1){
return "1";
}
//递归调用
string str = countAndSay(n-1);
int len = static_cast<int>(str.length());
int count = 1;
stringstream s;
for(int i = 0; i < len; ++i){
if(str[i] == str[i+1]){
count++;
} else {
s << count << str[i];
count = 1;
}
}
return s.str();
}
};
