38. Count and Say

题目：

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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 sequence.

Note: The sequence of integers will be represented as a string.

链接： http://leetcode.com/problems/count-and-say/

题解：

String的问题。需要建立一个int count，一个String res， StringBuilder sb以及一个递增变量start。 start从1开始，这时 res = "1"，count = 1。在一个while循环里套用一个for循环，for循环从1开始，每次当前字符和之前字符一样时，增加count，不一样时则把结果append到sb里。for循环结束时，append最后的count和char。最后更新sb，res以及count。虽然是道easy题目，但从刚开始做leetcode就没思路，一直拖到现在。现在想一想，应该是题目太长的缘故... -_____-!!

Time Complexity - O(n!)， Space Complexity - O(m)， m为最长字符串长。

public class Solution {
    public String countAndSay(int n) {
        if(n <= 0)
            return "";
        
        int count = 1;
        String res = "1";
        StringBuilder sb = new StringBuilder();
        int start = 1;
        
        while(start < n) {
            for(int i = 1; i < res.length(); i++) {
                if(res.charAt(i) == res.charAt(i - 1)) {
                    count++;
                } else {
                    sb.append(count);
                    sb.append(res.charAt(i - 1));
                    count = 1;
                }
            }
            
            sb.append(count);
            sb.append(res.charAt(res.length() - 1));
            res = sb.toString();
            sb.setLength(0);
            start++;
            count = 1;
        }
        
        return res;
    }
}

二刷：

二刷就有了一些细节上的思考。

比如一开始的n = 1的时候，序列为"1"，我们初始化res = "1"。
接下来的while 循环从假设 n > 1开始递减。
1. 新建一个String s = res.toString() + "#"。这个"#"用来处理最后一个字符与倒数第二个字符相等这种边界情况。
2. Set res = res.setLength(0)，清空res
3. 从1到s.length()遍历s
  1. 假如s.charAt(i) == s.charAt(i - 1)，我们增加count = count + 1
  2. 否则我们可以把count和之前的字符读入到res中 - res.append(count), res.append(s.charAt(i - 1))，并且我们可以更新count = 1
返回结果
看到过follow up问最多有几种字符，最长的连续字符是多长，或者问为什么里面3是最大的字符。因为假如有3个3，读起来就是"33"，这时候序列减少一个3，下次再读取又到了"23"，所以最长连续不会超过3个相同字符，最大的字符是'3'。

Java:

public class Solution {
    public String countAndSay(int n) {
        if (n <= 0) {
            return "";
        }
        int count = 1;
        StringBuilder res = new StringBuilder("1");

        while (n > 1) {
            String s = res.toString() + "#";    //use '#' as end of string
            res.setLength(0);
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == s.charAt(i - 1)) {
                    count++;
                } else {
                    res.append(count);
                    res.append(s.charAt(i - 1));
                    count = 1;
                }
            }
            n--;
        }
        return res.toString();
    }
}

三刷:

发现自己确实不太会处理字符串相关的题目，每次都写不顺，还是要多加练习啊。

Java：

public class Solution {
    public String countAndSay(int n) {
        if (n <= 0) return "";
        StringBuilder sb = new StringBuilder();
        String s = "1";
        
        while (n > 1) {
            int count = 1;
            char lastChar = s.charAt(0);
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == lastChar) {
                    count++;
                } else {
                    sb.append(count).append(lastChar);
                    count = 1;
                    lastChar = s.charAt(i);
                }
            }
            sb.append(count).append(lastChar);
            s = sb.toString();
            sb.setLength(0);
            n--;
        }
        return s;
    }
}

Reference:

https://leetcode.com/discuss/75204/4-5-lines-python-solutions