12.Count and Say
前言:
这种题还是paper tiger类型,属于文字描述特别多,但是你提取出规律之后就是臭弟弟难度。
文字思想:
递归实现:
结束条件:n==1时,返回”1”。
拆分方法:
a)获取上一行的结果,也就是传参为n-1。
b)对上一行进行描述:因为描述的值是连续的,所以就双指针标记,遇见前后指针指向位置的字符不等时,就得出了一个描述。
例子:
当前n = 5, 先递归求上一行的值,也就是n = 4
当前n = 4, 先递归求上一行的值,也就是n = 3
当前n = 3, 先递归求上一行的值,也就是n = 2
当前n = 2, 先递归求上一行的值,也就是n = 1
n == 1,递归结束条件,返回”1”
当前n = 2, 上一行的值为:1
开始对上一行进行描述:
当前待处理:1
前指针指向的字符是: 1, 下标为:0
开始统计有多少个连续的 1
后指针从1开始
对1的描述为:有1个1
对上一行:1的描述最终为:11
当前n = 3, 上一行的值为:11
开始对上一行进行描述:
当前待处理:11
前指针指向的字符是: 1, 下标为:0
开始统计有多少个连续的 1
后指针从1开始
后指针指向字符1 == 前指针指向的字符1
计数值加1,为:2
对1的描述为:有2个1
对上一行:11的描述最终为:21
当前n = 4, 上一行的值为:21
开始对上一行进行描述:
当前待处理:21
前指针指向的字符是: 2, 下标为:0
开始统计有多少个连续的 2
后指针从1开始
后指针指向字符1 != 前指针指向的字符2
对2的描述为:有1个2
当前待处理:1
前指针指向的字符是: 1, 下标为:1
开始统计有多少个连续的 1
后指针从2开始
对1的描述为:有1个1
对上一行:21的描述最终为:1211
当前n = 5, 上一行的值为:1211
开始对上一行进行描述:
当前待处理:1211
前指针指向的字符是: 1, 下标为:0
开始统计有多少个连续的 1
后指针从1开始
后指针指向字符2 != 前指针指向的字符1
对1的描述为:有1个1
当前待处理:211
前指针指向的字符是: 2, 下标为:1
开始统计有多少个连续的 2
后指针从2开始
后指针指向字符1 != 前指针指向的字符2
对2的描述为:有1个2
当前待处理:11
前指针指向的字符是: 1, 下标为:2
开始统计有多少个连续的 1
后指针从3开始
后指针指向字符1 == 前指针指向的字符1
计数值加1,为:2
对1的描述为:有2个1
对上一行:1211的描述最终为:111221
n = 5的结果是:111221
代码:
积累:
1.递归代码的步骤。2.整体。
领取专属 10元无门槛券
私享最新 技术干货