0038.count-and-say.md

0038.Count-and-Say

Description

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     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 _n_th term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Tags: String

题解

题意：这道题的意思特别刚，不太好理解

初始值第一行是 1。
第二行读第一行，1 个 1，去掉个字，所以第二行就是 11。
第三行读第二行，2 个 1，去掉个字，所以第三行就是 21。
第四行读第三行，1 个 2，1 个 1，去掉所有个字，所以第四行就是 1211。
第五行读第四行，1 个 1，1 个 2，2 个 1，去掉所有个字，所以第五航就是 111221。
第六行读第五行，3 个 1，2 个 2，1 个 1，去掉所以个字，所以第六行就是 312211。
然后题目要求输入 1 - 30 的任意行数，输出该行是啥。

思路1

直接按照从2到n的顺序生成字符串，即每次找连续相同的数字段，合并。

func countAndSay(n int) string {
    if n < 1 {
        return ""
    }

    say := []byte("1")
    for i := 0; i < n-1; i++ {
        var cnt byte
        var nextSay []byte
        for j := 0; j < len(say); j++ {
            cnt++
            if j == len(say)-1 || say[j] != say[j+1] {
                nextSay = append(nextSay, 48 + cnt, say[j]) // 48 - the ASCII code point of "0"
                cnt = 0
            }
        }
        say = nextSay
    }
    return string(say)
}

思路2

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm