Leetcode(38) Count and Say

发表于 | 更新于 | 分类于

Description:

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 _n_th 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”

解法：

首先理解题意。简而言之，就是这一个数对应字符串的生成由前一个数的字符串决定。具体来说，从前一个字符串的第一个字符数起，数相同字符的个数，然后将个数与该字符存入本数对应的字符串，再继续扫描计数。比如，对于4而言，前一个数3的字符串为21，则4为1个2一个1，即1211。可以发现，每一个数与前一个数的结果有关，采用递归实现，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String countAndSay(int n) {
        if(n == 1){
            return "1";
        }
        String str = countAndSay(n-1) +'*';  //防止越界，方便计数
        char[] cstr = str.toCharArray();
        String result = "";
        int count = 1;
        for(int i = 0;i<cstr.length - 1;i++){
            if(cstr[i] == cstr[i+1]){
                count +=1;
            }
            else{
                result += (String.valueOf(count) + cstr[i]) ;
                count = 1;
            }
        }
        return result;
    }
}