leetCode 38.Count and Say (計數和發言) 解題思路和方法

leetCode 38.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.

 

思路：題意實在太難理解了，尤其是英文又不好，只能參看下別人的資料，理解下規則。終於理解，題意是n=1時輸出字符串1；n=2時，數上次字符串中的數值個數，因為上次字符串有1個1，所以輸出11；n=3時，由於上次字符是11，有2個1，所以輸出21；n=4時，由於上次字符串是21，有1個2和1個1，所以輸出1211。依次類推，寫個countAndSay(n)函數返回字符串。

題意理解之後就好辦了，是典型的遞歸問題，其代碼很簡單，如下：

 

public class Solution {
    public String countAndSay(int n) {
        if(n == 1){
            return 1;
        }
        //遞歸調用，然後對字符串處理
        String str = countAndSay(n-1) + *;//為了str末尾的標記，方便循環讀數
        char[] c = str.toCharArray();
        int count = 1;
        String s = ;
        for(int i = 0; i < c.length - 1;i++){
        	if(c[i] == c[i+1]){
        		count++;//計數增加
        	}else{
        		s = s + count + c[i];//上面的*標記這裡方便統一處理
        		count = 1;//初始化
        	}
        }
        return s;
    }
}