Count and Say

出处

报数指的是，按照其中的整数的顺序进行报数，然后得到下一个数。如下所示：

1, 11, 21, 1211, 111221, ...

• 1 读作 one 1 -> 11.
• 11 读作 two 1s -> 21.
• 21 读作 one 2, then one 1 -> 1211.

给定一个整数 n, 返回 第 n 个顺序。

样例

给定 n = 5, 返回 "111221".

注意

整数的顺序将表示为一个字符串。

Solution

按照规则进行递推即可

Complexity

时间复杂度 O(n² )，空间复杂度 O(1)

Code

public class Solution {
    public String countAndSay(int n) {
        StringBuffer s = new StringBuffer("1");
        StringBuffer res = new StringBuffer();
        while((--n) != 0){
            res.setLength(0);
            int size = s.length();
            int cnt = 1;
            char cur = s.charAt(0);
            for(int i=1;i<size;i++){
                if(s.charAt(i)!=cur){
                    res.append(cnt);
                    res.append(cur);
                    cur = s.charAt(i);
                    cnt = 1;
                }else ++cnt;
            }
            res.append(cnt);
            res.append(cur);
            StringBuffer tmp = s;
            s = res;
            res = tmp;
        }
        return s.toString();
    }
}