报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1

输入: 1
输出: "1"

示例 2:

输入: 4
输出: "1211"

解决方法：利用递归和双指针法，
Go语言版本实现如下：

package count_and_say

func countAndSay(n int) string {
    buf := []byte{'1'}

    for n > 1 {
        buf = say(buf)
        n--
    }
    return string(buf)
}
func say(buf []byte) []byte {
    //res 的 长度不会超过 buf 的两倍，所以，可以事先指定容量，加快append 的速度
    res := make([]byte, 0, len(buf)*2)

    i, j := 0, 1
    for i < len(buf) {
        for j < len(buf) && buf[j] == buf[i] {
            j++
        }
        // res 中 res[i] 表示 res[i+1] 的个数，i 为0,2,4,6,...
        res = append(res, byte(j-i+'0'), buf[i])
        // 移动 i 到 j
        i = j
    }

    return res
}


package count_and_say

import (
    "fmt"
    "github.com/stretchr/testify/assert"
    "testing"
)

type question struct {
    para
    ans
}
type para struct {
    one int
}

type ans struct {
    one string
}

func TestCountAndSay(t *testing.T) {
    ast := assert.New(t)

    qs := []question{
        question{
            para{1},
            ans{"1"},
        },
        question{
            para{2},
            ans{"11"},
        },

        question{
            para{3},
            ans{"21"},
        },

        question{
            para{4},
            ans{"1211"},
        },

        question{
            para{5},
            ans{"111221"},
        },

        question{
            para{6},
            ans{"312211"},
        },

        question{
            para{7},
            ans{"13112221"},
        },

        question{
            para{20},
            ans{"11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211"},
        },
    }

    for _, q := range qs {
        a, p := q.ans, q.para
        fmt.Printf("~~%v~~\n", p)

        ast.Equal(a.one, countAndSay(p.one), "输入:%v", p)
    }
}