(Medium) LeetCode - Count and Say

tags: Go

category: LeetCode

description: LeetCode - Count and Say

created_at: 2021/08/05 15:00:00

題目連結: https://leetcode.com/problems/count-and-say/

前言

我覺得這個題目比較困難的地方在於題目的描述，看懂題目之後就好解很多，因為我題目也看了一陣子，想說介紹一下這個題目在幹嘛。說不定有人跟我一樣一開始看不懂題目

簡介

這個題目主要就是要你是實現一個 countAndSay(n) 的函數，而 countAndSay(n) 的答案會與 countAndSay(n-1) 有關。

而 countAndSay(1) 就輸出1。

看到這邊如果會寫遞迴的人應該直覺就是遞迴，但是實際上如果不遞迴也能寫的話就不見得要使用遞迴，畢竟大多情況純遞迴會比較慢。

他的題目主要就是去數數字，以他題目舉例的數字 3322251 ，就是 2個3，3個2，1個5，1個1，所以輸出23321511

而上面有提到說第 n 個答案會與 n-1 個答案有關，所以

f(1) = 1
f(2) = 11  => f(1)有1個1
f(3) = 21  => f(2)有2個1
f(4) = 1211  => f(3)有1個2，1個1
...
依此類推

這題就這樣的邏輯，然後底下附上用 Go 寫一個比較好理解的解法 (非遞迴)

import (
    "fmt"
    "strconv"
)

// 最大值
const MAX_N = 30

func countAndSay(n int) string {
    // 邊界判斷
    if n < 1 || n > MAX_N {
        return "0"
    }

    // 存放結果的串列
    nums := make([]string, MAX_N + 1)
    // 預設1為"1"
    nums[1] = "1"

    // 從2開始求值到n
    for i := 2; i <= n; i++ {
        // 要數前一個結果的答案
        num := nums[i-1]
        // 一開始跟第0個數比對
        index := 0
        // 數字存在則count一定大於1，不會有0個數字
        count := 1
        output := ""
        //從第一個開始數，比較值就是第0個
        for j := 1; j < len(num); j++ {
            // 如果第j個等於比較值就把count+1
            if num[index] == num[j] {
                count += 1
            } else {
                // 碰到不同的數字，更新比較值與count並更新輸出
                output += strconv.Itoa(count) + num[index: index+1]
                count = 1
                index = j
            }
        }
        // 最後跳出的時候會有最後一組數字的結果，要記得接回output
        output += strconv.Itoa(count) + num[index: index+1]
        // 一輪走完，把output存起來
        nums[i] = output
    }

    // 把第n個結果回傳
    return nums[n]
}