今天是紀錄LeetCode解題的第三十八天

第三十八題題目：The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) = "1"
• countAndSay(n) is the run-length encoding of countAndSay(n - 1).

Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string "3322251" we replace "33" with "23", replace "222" with "32", replace "5" with "15" and replace "1" with "11". Thus the compressed string becomes "23321511".

Given a positive integer n, return the nth element of the count-and-say sequence.

計數並說出序列是由遞迴公式定義的數字字串序列

變動長度編碼是一種字串壓縮方法，其原理是將連續的相同字元替換為數量加字元的連接，例如要壓縮字串"3322251"，我們將"33"替換為"23"，"222"替換為"32"，"5"替換為"15"，"1"替換為"11"，壓縮後的字串變為"23321511"

給定一個正整數n，回傳計數並說出序列的第nth個數

解題思路

先定義第一項為1，從第二個字元開始遍歷，如果nums[i]和nums[i-1]相同count+=1，否則記錄count+nums[i-1]，然後重設count=1

程式碼

class Solution:
    def countAndSay(self, n: int) -> str:
        result = "1"
        for _ in range(n - 1):
            temp = ""
            count = 1
            for i in range(1, len(result) + 1):
                if i < len(result) and result[i] == result[i - 1]:
                    count += 1
                else:
                    temp += str(count) + result[i - 1]
                    count = 1
            result = temp
        return result

執行過程

初始狀態

• n = 4
• result = "1"

第一次執行(result = "1",i in range(1,2))

• temp = ""
• count = 1
• i = 1
• i < len(result) and result[i] == result[i - 1] → False
• temp += str(count) + result[i - 1] → temp = "11"
• count = 1
• result = "11"

第二次執行(result = "11",i in range(1,3))

• temp = ""
• count = 1
• i = 1
• i < len(result) and result[i] == result[i - 1] → True
• count += 1 = 2

第三次執行(result = "11",i in range(1,3))

• i = 2
• i < len(result) and result[i] == result[i - 1] → False
• temp += str(count) + result[i - 1] → temp = "21"
• count = 1
• result = "21"

第四次執行(result = "21",i in range(1,3))

• temp = ""
• count = 1
• i = 1
• i < len(result) and result[i] == result[i - 1] → False
• temp += str(count) + result[i - 1] → temp = "12"
• count = 1

第五次執行(result = "21",i in range(1,3))

• i = 2
• i < len(result) and result[i] == result[i - 1] → False
• temp += str(count) + result[i - 1] → temp = "12" + "11" = "1211"
• count = 1
• result = "1211"