38、报数--leetcode

it2022-05-05  102

题目描述:

报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:

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"

算法分析设计: 关键是在理解题目意思上面:

1. 1 \ 2. 11 2.这个数报上面1.的数 3. 21 ... 4. 1211 \ 5. 111221 5.这个数报的是4.的数 ...一直下去

分析: n = 1 --对应–>1直接返回res=1,特殊的值 n = 2 --对应–>就将n = 1时候,res = 1 传入推导 -->得到结果res = 11 n = 3 --对应–>就将n = 2时候,res = 11传入推导(这个结果是经过i=1,i = 2推导迟来的)–>得到结果res = 21 n = 4 --对应–>就将n = 3时候,res = 21传入推导(这个结果是经过i=1,i = 2,i = 3推导出来的) -->得到结果res = 1211

...... 如此重复下去,知道退出结果

使用Python3实现的代码逻辑如下:

class Solution: def countAndSay(self, n: int) -> str: # 传入的是一个n(待报数),返回的是对n的报数字符串 def next_num(tmp): res = "" i = 0 tmp_n = len(tmp) while i < tmp_n: count = 1 while i < tmp_n - 1 and tmp[i] == tmp[i+1]: count += 1 i += 1 res = res + (str(count) + tmp[i]) i += 1 return res # 初始化第一个报数结果就是1,如果传入的n=1,返回的就是1. res = "1" for i in range(1,n): # 不断遍历传入的数,由前一个推出后一个,res右边的值赋值给左边的值。 res = next_num(res) return res

最新回复(0)