Labels

Thursday, January 29, 2015

Count and Say


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.

Naive Way: 很有趣的题目。第一次写就成功了,看来是一道简单的题目。通过读取上一次的String生成当前的String。

public class Solution {
    public String countAndSay(int n) {
        String str = "1";
        for(int i = 2;i <= n;i++){
            int j = 0;
            String newStr = "";
            while(j < str.length()){
                int count = 1;
                while(j+count < str.length()){
                    if(str.charAt(j)!=str.charAt(j+count))
                        break;
                    count++;
                }
                newStr += (char)(count+'0');
                newStr += str.charAt(j);
                j += count;
            }
            str = newStr;
        }
        return str;
    }
}

Improved Way: Discuss里有用recursive写的,感觉会更舒服些。

 

No comments:

Post a Comment