38. Count and Say
計數和報數序列是一個由遞歸公式定義的數字字符串序列：
countAndSay(1) = "1" countAndSay(n) 是 countAndSay(n - 1) 的運行長度編碼（RLE）。 運行長度編碼（RLE）是一種字符串壓縮方法，它通過將連續相同的字符（重複 2 次或更多次）替換為字符和標記字符數量的數字（運行長度）的連接來工作。例如，要壓縮字符串 "3322251"，我們將 "33" 替換為 "23"，將 "222" 替換為 "32"，將 "5" 替換為 "15"，並將 "1" 替換為 "11"。因此，壓縮後的字符串變為 "23321511"。
給定一個正整數 n，返回計數和報數序列的第 n 項。
範例 1：
輸入：n = 4
輸出："1211"
解釋：
countAndSay(1) = "1" countAndSay(2) = RLE of "1" = "11" countAndSay(3) = RLE of "11" = "21" countAndSay(4) = RLE of "21" = "1211"
Python
class Solution:
def countAndSay(self, n: int) -> str:
if n == 1:
return "1"
def next_number(s: str) -> str:
result = []
i = 0
while i < len(s):
count = 1
while i + 1 < len(s) and s[i] == s[i + 1]:
i += 1
count += 1
result.append(str(count) + s[i])
i += 1
return ''.join(result)
current = "1"
for _ in range(n - 1):
current = next_number(current)
return current
16.60MB, 42ms
C++
#include <string>
using namespace std;
class Solution {
public:
string countAndSay(int n) {
if (n == 1) return "1";
string current = "1";
for (int i = 2; i <= n; ++i) {
current = nextNumber(current);
}
return current;
}
private:
string nextNumber(const string& s) {
string result;
int i = 0;
while (i < s.size()) {
int count = 1;
while (i + 1 < s.size() && s[i] == s[i + 1]) {
++i;
++count;
}
result += to_string(count) + s[i];
++i;
}
return result;
}
};
8.84MB, 0ms
Javascript
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function(n) {
if (n === 1) return "1";
const nextNumber = (s) => {
let result = "";
let i = 0;
while (i < s.length) {
let count = 1;
while (i + 1 < s.length && s[i] === s[i + 1]) {
i++;
count++;
}
result += count.toString() + s[i];
i++;
}
return result;
};
let current = "1";
for (let i = 2; i <= n; i++) {
current = nextNumber(current);
}
return current;
};
51.45MB, 56ms
