報數序列是一個整數序列,按照其中的整數的順序進行報數,得到下一個數。其前五項如下:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被讀作 "one 1" ("一個一") , 即 11。
11 被讀作 "two 1s" ("兩個一"), 即 21。
21 被讀作 "one 2", "one 1" ("一個二" , "一個一") , 即 1211。
給定一個正整數 n(1 ≤ n ≤ 30),輸出報數序列的第 n 項。
注意:整數順序将表示為一個字元串。
示例 1:
輸入: 1
輸出: "1"
示例 2:
輸入: 4
輸出: "1211"
思路
手動模拟報數的過程,逐漸遞推就好了
一個很妙的解法是利用itertools的groupby方法,會自動幫我們完成數數的過程,用法距離如下:
[k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
[list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
Code
from itertools import groupby
class Solution:
def countAndSay(self, n: int) -> str:
prev = '1'
for i in range(1,n): # 計算n-1次
cnt = 0
tmp = ''
pos_char = prev[0]
length = len(prev)
for j in range(length): # 數數的過程
if prev[j] != pos_char:
tmp += str(cnt) + pos_char
cnt = 1
pos_char = prev[j]
else:
cnt += 1
tmp += str(cnt) + pos_char
prev = tmp # 完成一次更新
return prev
# 利用了itertools的解法
from itertools import groupby
class Solution:
def countAndSay(self, n: int) -> str:
prev = '1'
for i in range(1,n):
prev = ''.join([str(len(list(g))) + k for k,g in groupby(prev)])
return prev
注明