本文讲述了python基础编程100例：第99期-基础结构：字符串 外观数列！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第99期-基础结构：字符串 外观数列

1.问题描述

给定一个正整数n ，输出外观数列的第 n 项。 
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。 
你可以将其视作是由递归公式定义的数字字符串序列： 
1. countAndSay(1) = "1" 
2. countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。 
前五项如下：

1.    1
2.    11
3.     21
4.   1211
5.    111221

第一项是数字 1 

描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11" 

描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21" 

描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211" 

描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

例如，数字字符串 "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"

示例 3:

输入: n = 8 
输出: "1113213211"

from typing import List

class Solution:

    def countAndSay(self, n: int) -> str:

        #在此之间填写代码

print(Solution().countAndSay(1))

print(Solution().countAndSay(4))

print(Solution().countAndSay(8))

2.解题思路

• 标签：字符串
• 使用递归函数，从n、n-1、n-2依次往前直到1
• 分别计算每次的外观数列

3.解题方法

from typing import List

class Solution:

    def countAndSay(self, n: int) -> str:

        if n==1:return '1'

        x,y=0,''

        a=self.countAndSay(n-1)

        while x < len(a):

            m=1

            while x+1<len(a) and a[x]==a[x+1]:

                m+=1

                x+=1

            y=y+str(m*10+int(a[x]))

            x+=1

        return y

print(Solution().countAndSay(1))

print(Solution().countAndSay(4))

print(Solution().countAndSay(8))

算法讲解

这里用到了基础算法：递归，简单讲解下这个算法： 
什么是递归 
程序调用自身的编程技巧称为递归 
递归做为一种算法在程序设计语言中广泛应用。

递归算法一般用于解决三类问题： 
(1)数据的定义是按递归定义的。（Fibonacci函数） 
(2)问题解法按递归算法实现。 
(3)数据的结构形式是按递归定义的。

递归函数特征 
必须有一个明确的结束条件； 
每次进入更深一层递归时，问题规模相比上次递归都应有所减少 
相邻两次重复之间有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）。
递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。