38. Count and Say

题目描述：

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.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

题目翻译

“计数与描述”序列如下所示：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1被读取为"1个1"或11。 11被读取为"2个1"或21。 21被读取"1个2，然后1个1"或1211。 给定一个整数n，生成count-and-say序列的第n个项。

注意：整数序列中的每个项将被表示为一个字符串。

示例1：

输入： 1
输出： “1”

示例2：

输入： 4
输出： “1211”

解题方案

标签： String

思路：

• 使用递归实现，递归表达式如下
  • 当 n == 1 时，返回"1"
  • 当 n != 1 时，返回n-1时的结果，返回后对其进行描述解析
• 描述解析过程如下
  • 遍历字符串
  • 当前字符与前一个字符相同时，长度+1
  • 字符不同时，将该描述记录下来
  • 返回解析好的字符串

代码：

class Solution {
    public String countAndSay(int n) {
        if(n == 1)
            return "1";
        else{
            String str = countAndSay(n-1);
            String res="";
            int len = 1;
            int i = 1;
            while(i<str.length()){
                if(str.charAt(i) == str.charAt(i-1)){
                    len++;
                }else{
                    res+=String.valueOf(len) + String.valueOf(str.charAt(i-1));
                    len = 1;
                }
                i++;
            }
            res+=String.valueOf(len) + String.valueOf(str.charAt(i-1));
            return res;
        }
    }
}