python数列求和1+11+111前n项_Leetcode Python算法(11)-----外观数列
原题重现:day011
这题目是相当的绕口,其实我是不会做的,所以参考了一下大神的答案。
class Solution:
def countAndSay(self, n: int) -> str:
prev_person = '1'
for i in range(1, n): #要处理的层数
next_person = ''
num = prev_person[0]
count = 1
for j in range(1, len(prev_person)):
if prev_person[j] == num: #j在num后一个查找
count += 1
else:
next_person += str(count) + num
count = 1
num = prev_person[j]
next_person += str(count) + num
prev_person = next_person
return prev_person
该代码在我看来就是还原了题目说明的流程。从第一个字符串“1”开始,被比较的数字num从pre_peerson第一个开始,第二个和第一个比较以此类推。如果重复就计数器加一,如果不相等的话就添加到字符串当中,同时计数器重置为1,num顺移到下一个。最后加上最后一个字符串和它的计数值。
之后又学习了第二个版本的解题思路,用的是递归的思想。
class Solution:
def countAndSay(self, n: int) -> str:
if n <= 1:
return '1'
pre = self.countAndSay(n - 1)
for idx in range(len(pre)):
if idx == 0: #准备工作
count = 1
res = ''
elif pre[idx] != pre[idx -1]: #后一个值不等于前面那个
res += str(count) + pre[idx-1]
count = 1
elif pre[idx] == pre[idx-1]:
count += 1
if idx == len(pre) - 1: #加上最后一个数字的数目和它本身
res += str(count) + pre[idx]
return res
这里的思路也很清晰,基条件是当n< = 1 时返回值为1,之后不断地往上垒。比较需要注意的是idx等于0和等于idx等于最后一个的时候需要单独处理。
打卡day011