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

Python是一门需要不断实践练习的编程语言,本文档将AI大学堂学员交流群的Python每周练习进行汇总,希望各位小伙伴能够多进行实践练习,逐渐爱上这门神奇的编程语言,掌握它并在生活中能够使用它。

# 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" 的描述如下图:
image.jpg

示例 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))
1
2
3
4
5
6
7
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

第1-3,16-18行: 题目中已经给出的信息,运行代码时要根据这些代码进行编辑
第4行: 当n=1时,直接返回1,也是结束条件
第5行: 定义变量x,y并分别赋值索引0,空字符串''
第6行: 定义变量a等于n-1时的外观数列
第7行: 当索引x值小于上一个外观数列长度时,执行循环
第8行: 定义变量m=1用于记录当前值的数量
第9行: 判断x+1是否还在外观数列内且索引x+1对应的值是否与x对应的值相等,若是,执行循环
第10-11行: 循环中,数量m加一,索引x加一,进行下次循环
第12行: 按照定义,给字符串上加上当前数字的数量和以及次数字
第13行: 索引x加一,进行下次循环
第14行: 当索引x大于外观数列长度时,结束循环并返回字符串y

代码运行结果为:
image.jpg

# 算法讲解

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


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


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

# 4 视频解析

高清视频讲解,请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号,发送 python100 即可领取Python基础实战100例源代码
AI大学堂公众号.png

更新于: 12/28/2021, 7:43:14 AM