LeetCode第38題

  • 2019 年 10 月 7 日
  • 筆記

LeetCode第38題

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

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 where 1 ≤ n ≤ 30, 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: 1Output: "1"

Example 2:

Input: 4Output: "1211"

翻譯：

簡單來說就是：

第一次：1

第二次：一個1：11

第三次：兩個1：21

第四次：一個2，一個1：1211

第五次：一個1，一個2，兩個1：111221

第六次：三個1，兩個2，一個1：312211

以此類推...

思路：

首先想想每一次的比較，肯定是首先固定一個數值，然後循環遍歷與其相比較

for(int i = 1;i<value.length();i++){   if(temp == value.charAt(i)){       count++;   }else{       //第一次出現不相等       result.append(count).append(temp);       count = 1;       temp = value.charAt(i);   }}

else方法塊里的就是關鍵：一旦出現不相等的情況，就append前面的結果，然後更新那個固定值，接著繼續遍歷比較

最外面的話很明顯就是採用遞歸了，從1開始，一輪一輪的計算上去，直到想要的結果

String result = "1";while(--n>0){    result = getOnce(result);    System.out.println(result);}

完整程式碼如下

class Solution {    public String countAndSay(int n) {       String result = "1";        while(--n>0){            result = getOnce(result);            System.out.println(result);        }        return result;            }        public String getOnce(String value){        StringBuffer result = new StringBuffer();        char temp = value.charAt(0);        int count = 1;        for(int i = 1;i<value.length();i++){           if(temp == value.charAt(i)){               count++;           }else{               //第一次出現不相等               result.append(count).append(temp);               count = 1;               temp = value.charAt(i);           }        }        return result.append(count).append(temp).toString();    }}

每次遞歸列印的結果就是:

11 21 1211 111221 312211

...

Tags:

VirMach 便宜 VPS