[leetcode]: 38. Count and Say

我不是女神ヾ 2022-06-15 09:22 261阅读 0赞

1.题目

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.
一个读数的序列1, 11, 21, 1211, 111221,…给定n求这个序列第n个string是什么。
Note: The sequence of integers will be represented as a string.

2.分析

读数的规律：从前往后读
一个数字x如果后面没有相邻的相同数字，则读作 1x
例如 1–》11，21–》12 11
一个数字x如果后面有相邻相同数字，一共有n个，则读作nx
例如 11–》21， 111221（3个1，2个2，1个1）–》312211

找到规律后遍历一遍字符串即可。注意序列从第1个开始，不是从第0个开始。

3.代码

  1. def countAndSay(self, n):
  2.     if n<1:
  3.         return 
  4.     elif n==1:
  5.         return "1"
  6.     cur="11"
  7.     next=""
  8.     for t in range(n-2):
  9.         i=0
  10.         while i<len(cur):
  11.             count=1
  12.             while i+count<len(cur) and cur[i]==cur[i+count]:
  13.                 count+=1
  14.             next+=str(count)+cur[i]
  15.             i+=count
  16.         cur=next
  17.         next=""
  18.     return cur

发表评论

表情：
评论列表 （有 0 条评论，261人围观）

还没有评论，来说两句吧...

相关阅读