119.报数

题号38：

报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1. 1

2. 11

3. 21

4. 1211

5. 111221

1 被读作 "one 1" ("一个一") , 即 11。

11 被读作 "two 1s" ("两个一"）, 即 21。

21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n ，输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

输入: 1

输出: "1"

示例 2:

输入: 4

输出: "1211"

解题思路：递归。

递归获取上一行的字符串，第一行为“1”；

假设已获取到的上一个字符串s0，对s0进行遍历统计，即可得到当前字符串。

代码实现：

class Solution {

public:

string countAndSay(int n) {

if(n==1) return "1";

string s0,s1;

s0=countAndSay(n-1);

for(int i=0;i

int tmp_count=1;

int j=i+1;

if(j

while(s0[j]==s0[i]){

j++;

tmp_count++;

}

}

s1+=tmp_count+'0';// tmp_count个s0[i]，数字转成字符

s1+=s0[i];

if(tmp_count>1)

i+=tmp_count-1;

}

return s1;

}

};