38. Count and Say（报数）

 

链接：https://leetcode-cn.com/problems/count-and-say/

 

题目：

 

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

　　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"

 

思路：

 

　　怎么说呢，一道题目很绕的简单题。思路就是每次得到的都是基于上次的字符串，第三次21，一个2一个1，第四次就是1211，第五次就是11+12+21，以此类推。找到规律之后就是简单的遍历了。

 

代码：

 

 1 public static String countAndSay(int n) {
 2     String str = "1";
 3 
 4     for (int i = 2; i <= n; i++) {
 5       StringBuilder sb = new StringBuilder();
 6       char old = str.charAt(0);
 7       int num = 1;
 8       for (int j = 1; j < str.length(); j++) {
 9         char one = str.charAt(j);
10         if (one == old) {
11           num++;
12         } else {
13           sb.append(num);
14           sb.append(old);
15           old = one;
16           num = 1;
17         }
18       }
19       sb.append(num);
20       sb.append(old);
21       str = sb.toString();
22     }
23 
24     return str;
25   }