Count and Say ใน Python

ที่นี่เราจะดูลำดับ 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
  • while j < ความยาวของ s:
    • ถ้า curr เป็น "" ให้ curr := s[j], count := 1 และเพิ่ม j ขึ้น 1
    • else if 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):
                if curr == "":
                    curr = s[j]
                    count = 1
                    j += 1
                elif curr == s[j]:
                    count += 1
                    j += 1
                else:
                    temp += str(count) + curr
                    curr = ""
                    count = 0
            temp += str(count) + curr
            s = temp
        return s

ob1 = Solution()
print(ob1.countAndSay(6))

อินพุต

print(ob1.countAndSay(6))

เอาต์พุต

312211