The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1 2. 11 3. 21 4. 1211 5. 111221
1
is read off as "one 1"
or 11
.11
is read off as "two 1s"
or 21
.21
is read off as "one 2
, then one 1"
or 1211
.
Given an integer n, generate the nth term of the count-and-say sequence.
这道题的要求是数数并记录,生成序列中第n个字符串。
序列中第一个字符串是“1”,接下来依次统计前一个字符串中连续相同字符的数量,并添加到下一字符串中。前15字符串如下:
每一行都是上一行的数数结果,例如,第五行的’111221’:代表第四行‘1211’有1个1,1个2,2个1,连起来就是11-12-21,即111221。
. 1 . 11 . 21 . 1211 . 111221 . 312211 . 13112221 . 1113213211 . 31131211131221 . 13211311123113112211 . 11131221133112132113212221 . 3113112221232112111312211312113211 . 1321132132111213122112311311222113111221131221 . 11131221131211131231121113112221121321132132211331222113112211 . 311311222113111231131112132112311321322112111312211312111322212311322113212221
例如,输入‘1’ ,输出第一行的1
输入‘4’,输出第四行的‘1211’
常规算法:输入n,要想得到第n行的序列,可以从第一行的‘1’开始,一行一行来算,直到n行 返回结果。
class Solution { public: string countAndSay(int n) { if (n == 0) return ""; string res = "1"; while (--n) { //输入n时,一行一行算,直到算到第n行 string cur = ""; for (int i = 0; i < res.size(); i++) { int count = 1; while ((i + 1 < res.size()) && (res[i] == res[i + 1])){ //正在统计当前字符的数量 count++; i++; } cur += to_string(count) + res[i]; //一个字符统计完后,记录它的数量及本身。to_string(count)代表res[i]的数量 } res = cur; } return res; } };