leetcode-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(1 ≤ n ≤ 30),输出报数序列的第 n 项。

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

示例 1:

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

这题......有点不好理解。

解释下题意,可能有同学看不懂。

题意true

下一个字符串由上一个字符串来决定 。

比如

上一个是1,下一个就是1个1,即 "11";

上一个是21,下一个就是 1个2,1个1,即"1211";

上一个是111221,下一个就是3个1,2个2,1个1,即"312211"。

算法

  1. 定义string raw, ans(raw为最终输出结果, ans为存储中间结果的临时字符串)
  2. 根据输入整数确定更新次数
  3. 每次遍历原始字符串(初始为"1",每次循环结束后更新)
  4. 对重复出现的字符予以计数,计数完毕后将出现的次数和字符添加在ans末尾
  5. 将ans赋给raw, ans置空,继续。
  6. 返回raw

code

 1 class Solution {
 2 public:
 3     string countAndSay(int n) {
 4         if(n == 1)
 5             return "1";
 6         string raw = "1";
 7         string ans = "";
 8         n--;
 9         while(n--)
10         {
11             for(int i=0; i<raw.length();)
12             {
13                 int begin = i;
14                 while(raw[i] == raw[begin])
15                 {
16                     i++;
17                 }
18                 char c = i-begin + '0';
19                 ans = ans + c + raw[begin];
20             }
21             raw = ans;
22             ans = "";
23         }
24         
25         return raw;
26     }
27 };

 附上1:10 的测试样例

The following are the terms from n=1 to n=10 of the count-and-say sequence:

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
10.     13211311123113112211