38. Count and Say

Question:

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 where 1 ≤ n ≤ 30, 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"

Thinking:

• Method:回溯
  1. 每一个当前的解都是基于上一个解。
  2. 通过回溯获得上一个解。
  3. 对上一个进行分析，获得当前的解。

class Solution {
    public String countAndSay(int n) {
        if(n == 1)
            return "1";
        else{
            String current = countAndSay(n - 1);
            StringBuilder sb = new StringBuilder();
            int index = 0;
            char pre = current.charAt(index);
            int count = 0;
            while(index < current.length()){
                char c = current.charAt(index);
                if(c == pre){
                    count++;
                }else{
                    sb.append(count);
                    sb.append(pre);
                    pre = c;
                    count = 1;
                }
                if(index == current.length() - 1){
                    sb.append(count);
                    sb.append(c);
                }
                index++;
            }
            return sb.toString();
        }
    }
}

二刷

这种题目还是要通过回溯方法获得上次一的结果。 每次获取上一次的结果，再通过解析上一次的结果，获得当前结果。

class Solution {
    public String countAndSay(int n) {
        if(n == 1) return "1";
        else{
            String last = countAndSay(n - 1);
            char[] arr = last.toCharArray();
            StringBuilder sb = new StringBuilder();
            int count = 1;
            for(int i = 1; i < arr.length; i++){
                if(arr[i] == arr[i - 1]) count++;
                else{
                    sb.append(new Integer(count).toString());
                    sb.append(arr[i - 1]);
                    count = 1;
                }
            }
            sb.append(new Integer(count).toString());
            sb.append(arr[arr.length - 1]);
            return sb.toString();
        }
    }
}