Go Java算法之外觀數列實現方法示例詳解
外觀數列
給定一個正整數 n ,輸出外觀數列的第 n 項。
「外觀數列」是一個整數序列,從數字 1 開始,序列中的每一項都是對前一項的描述。
你可以將其視作是由遞歸公式定義的數字字符串序列:
countAndSay(1) = "1"
countAndSay(n) 是對 countAndSay(n-1) 的描述,然後轉換成另一個數字字符串。
前五項如下:
- 1、1 —— 第一項是數字 1
- 2、11 —— 描述前一項,這個數是 1 即 “ 一 個 1 ”,記作 "11"
- 3、21 —— 描述前一項,這個數是 11 即 “ 二 個 1 ” ,記作 "21"
- 4、1211 —— 描述前一項,這個數是 21 即 “ 一 個 2 + 一 個 1 ” ,記作 "1211"
- 5、111221 —— 描述前一項,這個數是 1211 即 “ 一 個 1 + 一 個 2 + 二 個 1 ” ,記作 "111221"
方法一:遍歷生成(Java)
所謂的「外觀數列」,其實本質上隻是依次統計字符串中連續相同字符的個數。
題目中給定的遞歸公式定義的數字字符串序列如下:
countAndSay(1) = "1";
countAndSay(n) 是對 countAndSay(n-1) 的描述,然後轉換成另一個數字字符串。
我們定義字符串 S_{i}表示countAndSay(i),我們如果要求得 S_{n},則我們需先求出 S_{n-1},然後按照上述描述的方法生成,即從左到右依次掃描字符串 S_{n-1}中連續相同的字符的最大數目,然後將字符的統計數目轉化為數字字符串再連接上對應的字符。
class Solution { public String countAndSay(int n) { String str = "1"; for (int i = 2; i <= n; ++i) { StringBuilder sb = new StringBuilder(); int start = 0; int pos = 0; while (pos < str.length()) { while (pos < str.length() && str.charAt(pos) == str.charAt(start)) { pos++; } sb.append(Integer.toString(pos - start)).append(str.charAt(start)); start = pos; } str = sb.toString(); } return str; } }
N 為給定的正整數,M 為生成的字符串中的最大長度
時間復雜度:O(N * M)
空間復雜度:O(M)
方法二:遞歸(Go)
具體的方法分析已經在上文中表述
由於每次得到的數據都是來源於上一次的結果,所以我們可以假設得到瞭上次的結果,繼而往後運算。這就運用到瞭遞歸。
func countAndSay(n int) string { if n == 1 { return "1" } s := countAndSay(n - 1) i, res := 0, "" length := len(s) for j := 0; j < length; j++ { if s[j] != s[i] { res += strconv.Itoa(j-i) + string(s[i]) i = j } } res += strconv.Itoa(length-i) + string(s[i]) return res }
N 為給定的正整數,M 為生成的字符串中的最大長度
時間復雜度:O(N * M)
空間復雜度:O(M)
以上就是Go Java算法之外觀數列實現方法示例詳解的詳細內容,更多關於Go Java算法外觀數列的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- Go&java算法之最大數示例詳解
- Go Java算法猜數字遊戲示例詳解
- Go Java算法之單詞規律示例詳解
- Go Java 算法之字符串解碼示例詳解
- Go Java算法之字符串中第一個唯一字符詳解