Python中的Count and Say

这里我们将了解Count and Say序列。这是一个序列，其部分项如下所示：

  • 1
  • 11
  • 21
  • 1211
  • 111221

字符串将按如下方式读取

  • 1（一）
  • 11（一个1）所以读取前面的1，并说“一个1”
  • 21（两个1）所以读取前面的11，并说“两个1”
  • 1211（一个2一个1）所以读取前面的21，并说“一个2一个1”
  • 111221（一个1一个2两个1）所以读取前面的1211，并说“一个1一个2两个1”

假设我们有一个数字n，1 <= n < = 30，那么我们必须生成第n项。

为了解决这个问题，我们将遵循以下方法：

  • 设置s := “1”
  • 如果n = 1，则返回s
  • 对于i := 2到n + 1
    • j := 0，temp := “”，curr = “”和count := 0
    • 当j < s的长度时，执行
      • 如果curr是“”，则curr := s[j]，count := 1并将j增加1
      • 否则如果curr是s[j]，则将count和j增加1
      • 否则temp := temp + count作为字符串+ curr，curr = “”，count := 0
    • temp := temp + count作为字符串+ curr
  • 返回s

让我们看看以下实现以获得更好的理解：

示例

 实时演示

class Solution(object):
   def countAndSay(self, n):
      """
      :type n: int
      :rtype: str
      """
      s = "1"
      if n == 1:
         return s
      for i in range(2,n+1):
         j = 0
         temp = ""
         curr = ""
         count = 0
         while j<len(s):
            #print(curr,count)
            if curr =="":
               #print(curr)
               curr=s[j]
               count=1
               j+=1
            elif curr == s[j]:
               #print(curr)
               count+=1
               j+=1
            else:
               #print(count,curr)
               temp+= str(count) + curr
               curr=""
               count = 0
               #print(temp)
         temp+=str(count) + curr
         s=temp
      return s
ob1 = Solution()
print(ob1.countAndSay(6))

输入

print(ob1.countAndSay(6))

输出

312211

更新于： 2020年4月28日

1K+ 浏览量

开启你的职业生涯

通过完成课程获得认证

开始学习
广告