Leetcode -- 外观数列（38）

题目描述：「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。注意：整数序列中的每一项将表示为一个字符串。

具体思路：由题意可知，第n项的值是通过遍历第n-1项所得到的，即每一项都依赖于前一项，因而自然而然地想到采用递归的方法。（自然也可以用迭代法）

• 思路一：递归方法。用变量temp来存放上一项的值，即temp = countAndSay(n-1)。初始化count=1，ans=‘’，用ans记录最终结果。遍历temp中的每一个字符，当后一个字符与前一个字符相同时，则count++；否则，将count与最近遍历过的一个字符存入ans中，并更新count。

   1 class Solution:
   2     def countAndSay(self, n: int) -> str:
   3         if n == 1:
   4             return ‘1‘
   5         ans = ‘‘
   6         temp = countAndSay(n-1)    #递归
   7         i, count = 1  
   8         while (i < len(temp)):
   9             if temp[i] == temp[i-1]：    #因为i是从1开始的，即从第2的字符开始依次与其前一个字符比较
  10                 count += 1
  11             else:
  12                 ans += str(count) + temp[i-1]    #temp[i-1]表示刚遍历过的那个字符
  13                 count = 1
  14             i += 1
  15         ans += str(count)+temp[i-1]   #跳出while循环时，最后一个字符还未记录
  16         return ans

   

• 思路二：迭代方法。pre_str用来记录第n-1项的结果，next_str用来记录第n项。外层while循环控制遍历的是第几项，内层for循环遍历该项的每一个字符。由于每一项与其上一项相关，所以用num来记录上一项中出现的字符，count记录该字符出现了多少次。遍历pre_str, 当下一字符与当前字符相同时，则count++；否则，更新next_str为当前字符出现的次数count与当前字符num相连接，同时更新count=1、num=pre_str[j]. 注意每当内循环结束时，要加入最后一个字符及其出现的次数。

   1 class Solution:
   2     def countAndSay(self, n: int) -> str:
   3         if n == 1:
   4             return ‘1‘
   5         pre_str = ‘1‘
   6         i = 1
   7         while(i < n):
   8             next_str, num, count = ‘‘, pre_str[0], 1
   9             for j in range(1,len(pre_str)):
  10                 if pre_str[j] == pre_str[j+1]:
  11                     count += 1
  12                 else:
  13                     next_str = str(count)+num
  14                     num = pre_str[j]
  15                     count = 1
  16             #结束内循环后
  17             next_str += str(count)+num
  18             pre_str = next_str
  19             i += 1
  20         return pre_str

   

• 思路三：调用groupby函数。具体用法见：https://docs.python.org/zh-cn/3.8/library/itertools.html?highlight=groupby#itertools.groupby

   1 #groupby示例
   2 from itertools import groupby
   3 test = ‘11233355‘
   4 for k,g in groupby(test):
   5     print(k)
   6     print(list(g))
   7 
   8 #输出
   9 #1
  10 #[‘1‘, ‘1‘]
  11 
  12 #2
  13 #[‘2‘]
  14 
  15 #3
  16 #[‘3‘, ‘3‘, ‘3‘]
  17 
  18 #5
  19 #[‘5‘, ‘5‘]

  1 class Solution:
  2     def countAndSay(self, n: int) -> str:
  3         from itertools import groupby
  4         result = ‘1‘
  5         for i in range(1,n):
  6             result = ‘‘.join(str(len(list(g)))+k for k,g in groupby(result))
  7         return result    

   

Leetcode -- 外观数列（38）

原文：https://www.cnblogs.com/shawn-young/p/12493960.html