題目描述
外觀數(shù)列
給定一個正整數(shù) n ，輸出外觀數(shù)列的第 n 項。
「外觀數(shù)列」是一個整數(shù)序列，從數(shù)字 1 開始，序列中的每一項都是對前一項的描述。
你可以將其視作是由遞歸公式定義的數(shù)字字符串序列：
countAndSay(1) = "1"-
countAndSay(n)是對countAndSay(n-1)的描述，然后轉(zhuǎn)換成另一個數(shù)字字符串。
前五項如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一項是數(shù)字 1
描述前一項，這個數(shù)是 1 即 “ 一 個 1 ”，記作 "11"
描述前一項，這個數(shù)是 11 即 “ 二 個 1 ” ，記作 "21"
描述前一項，這個數(shù)是 21 即 “ 一 個 2 + 一 個 1 ” ，記作 "1211"
描述前一項，這個數(shù)是 1211 即 “ 一 個 1 + 一 個 2 + 二 個 1 ” ，記作 "111221"
要 描述 一個數(shù)字字符串，首先要將字符串分割為 最小 數(shù)量的組，每個組都由連續(xù)的最多 相同字符 組成。然后對于每個組，先描述字符的數(shù)量，然后描述字符，形成一個描述組。要將描述轉(zhuǎn)換為數(shù)字字符串，先將每組中的字符數(shù)量用數(shù)字替換，再將所有描述組連接起來。
例如，數(shù)字字符串 "3322251" 的描述如下圖：
示例 1：
輸入：n = 1
輸出："1"
解釋：這是一個基本樣例。
示例 2：
輸入：n = 4
輸出："1211"
解釋：
countAndSay(1) = "1"
countAndSay(2) = 讀 "1" = 一 個 1 = "11"
countAndSay(3) = 讀 "11" = 二 個 1 = "21"
countAndSay(4) = 讀 "21" = 一 個 2 + 一 個 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30
解法
依次統(tǒng)計字符串中連續(xù)相同字符的個數(shù)。
左到右依次掃描字符串 Sn?1中連續(xù)相同的字符的最大數(shù)目，然后將字符的統(tǒng)計數(shù)目轉(zhuǎn)化為數(shù)字字符串再連接上對應(yīng)的字符即可。
java代碼：文章來源：http://www.zghlxwxcb.cn/news/detail-786661.html
class Solution {
public String countAndSay(int n) {
String res = "1";
if (n == 1) {
return res;
}
for (int i = 1; i < n; i++) {
int count = 0;
StringBuilder newRes = new StringBuilder();
for (int j = 0; j < res.length(); j++) {
if (count == 0 || res.charAt(j) == res.charAt(j - 1)) {
count ++;
} else {
newRes.append(count).append(res.charAt(j - 1));
count = 1;
}
}
if (count != 0) {
newRes.append(count).append(res.charAt(res.length() - 1));
}
res = newRes.toString();
}
return res;
}
}
復(fù)雜度文章來源地址http://www.zghlxwxcb.cn/news/detail-786661.html
- 時間復(fù)雜度：
O(N×M)，其中 N 為給定的正整數(shù)，M 為生成的字符串中的最大長度。 - 空間復(fù)雜度：
O(M)。
到了這里，關(guān)于LeetCode 38 外觀數(shù)列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
