38. Count and Say (Easy) Facebook

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

1is read off as"one 1"or11.
11is read off as"two 1s"or21.
21is read off as"one 2, thenone 1"or1211.

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"

Solution 1: StringBuilder O(n); O(n)

the (i+1)th sequence is the “count and say” of the ith sequence!

其实我们可以发现字符串中永远只会出现1,2,3这三个字符，假设第k个字符串中出现了4，那么第k-1个字符串必定有四个相同的字符连续出现，假设这个字符为1，则第k-1个字符串为x1111y。第k-1个字符串是第k-2个字符串的读法，即第k-2个字符串可以读为“x个1,1个1,1个y” 或者“*个x,1个1,1个1,y个*”，这两种读法分别可以合并成“x+1个1,1个y” 和 “*个x，2个1，y个*”，代表的字符串分别是“(x+1)11y” 和 "x21y"，即k-1个字符串为“(x+1)11y” 或 "x21y"，不可能为“x1111y”.

    public String countAndSay(int n) {
        if (n == 0) {
            return "";
        }

        String s = "1";
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            int count = 1;
            for (int j = 1; j <= s.length(); j++) {
                if (j == s.length() || s.charAt(j - 1) != s.charAt(j)) {
                    sb.append(count);
                    sb.append(s.charAt(j - 1));
                    count = 1;
                } else {
                    count++;
                }
            }
            s = sb.toString();
        }
        return s;
    }

Follow Up:

1.还问了结果最长、最短能有多少

最长可以无限长，最短就1吧。。。

2.n是input的位数，时间复杂度是O(n)啊，只用扫一遍，最长是2n，最短是log10(n)+2 TODO

http://www.1point3acres.com/bbs/thread-320823-1-1.html