38. Count and Say 数数并说出

题目

首先，对于一个数字，例如 3322251，我们将其转换为 2个3，3个 2，1 个 5， 1个1，最终结果是 23321511。
基于此，我们给定一个迭代次数 n。从 1 开始，我们依次输出所有的结果。假设n为4。

1. 首先基数 为 1 ->1
2. 1个1 -> 11
3. 2个1 -> 21
4. 1个2一个1 -> 1211

解析

如果分开算，用字符串更简单。

1. 顺序遍历，如果相同就+1，不同就归 1。依次拼接新的字符串即可
2. 问题的关键点在于，我们是向前比较，还是向后比较。这样好做临界处理。
3. 个人喜欢向后比较，即最终循环遍历完成后，指针指向最后一个未进行匹配的元素。
4. 如果这个元素和前一个不同，则 count 被重置为 0，如果相同，前一个还未结算，所以只需要 count++ 然后append即可。

伪代码

say(strstring) string

count:=0
for i:=0;i<len(str)-1;i++
  count++
  if str[i]!= str[i+1]
     count=0
    rst = apend(rst,count,str[i])

count++
rst=append(rstm count, str[i])

代码

func countAndSay(n int) string {
    str:="1"
    for i:=1; i<n; i++ {
        str = say(str)
    }
    return str
}

func say(str string) string {
    var rst []byte
    var count int
    for i:=0; i<len(str)-1; i++ {
        count++
        if str[i] != str[i+1]{
            rst=append(rst, byte(count+'0'), byte(str[i]))
            count=0
        }
    }
    count++
    rst = append(rst, byte(count+'0'), byte(str[len(str)-1]))
    return string(rst)
}

成功的读错了题意，这也没说清楚，数字要是分开了是一起算还是单独算，下面解法写了一大堆合起来算的。

题目

首先，对于一个数字，例如 3322251，我们将其转换为 2个3，3个 2，1 个 5， 1个1，最终结果是 23321511。
基于此，我们给定一个迭代次数 n。从 1 开始，我们依次输出所有的结果。假设n为4。

1. 首先基数 为 1 ->1
2. 1个1 -> 11
3. 2个1 -> 21
4. 1个2一个1 -> 1211

解析

所以首先我们需要一个函数，这个函数入参是一个整数，出参是这个整数的 say 。然后迭代 n 次即可。
如何实现这个函数：
输入数据和输出数据的特点：结果顺序按每个数字出现的顺序。
我们要解决两个问题，1. 固定数字的出现顺序 2. 统计数字的出现次数。

1. 所以，首先我们需要判断数字是否已经出现

2. 数字出现的位置是第几个

3. 找到数字出现的位置并+1
   为了判断数字已经出现，我们可以1个数组，将其记为 loc。
   为了存储数字出现的次数，我们又需要另一个数组 count。
   这两个数组长度是固定的 10，表示数字 0~9，大多数语言的初始值为 0，为了避免这个无效索引情况，所以对于第二个统计数组，我们从 1 开始计数。

4. 设置 loc [10]int count[11]int，和 count 当前指针 flag = 1

5. 对于 num，依次遍历其末尾元素。更具 loc 找到 count 的存储位置+1。

6. 对于 更具 count 顺序，组合结果数据，这里我们需要扩展 count 为一个二维数组，[11][2]int 其中第一个数组存储 num，第二个数字存储count，这样才能计算结果数据。

伪代码

loc [10]int
count [11][2]int
flag = 1
for nums != 0
  pop = nums%10
  nums = nums/10
  l = loc[pop]
  if l == 0
    count[flag][0] = pop
    l = flag
    flag++
  num[l][1]++

for i:=11;i>=1;i--
  rst=rst*100 + count[i][1]*10 + count[i][0]
return rst

代码

func countAndSay(n int) string {
    rst:=1
    for i:=1; i<n; i++ {
        rst = say(rst)
    }
    return intToString(rst)
}

func say(num int) int {
    var rst int
    loc := [10]int{}
    count :=[11][2]int{{},{},{},{},{},{},{},{},{},{},{}}
    flag:=1
    
    for num != 0 {
        pop := num%10
        num=num/10
        l := loc[pop]
        if l == 0 {
            loc[pop]=flag
            count[flag][0] = pop
            l = flag
            flag++
        }
        count[l][1]++
    }
    for i:=10;i>=1;i--{
        if count[i][1] != 0 {
            rst=rst*100+count[i][1]*10 + count[i][0]
        }
    }
    return rst
}

func intToString(num int) string {
    var rst []byte
    for num != 0 {
        pop := num%10
        num=num/10
        rst = append(rst,byte(pop+'0'))
    }
    i:=0
    j:=len(rst)-1

    for i<j {
        rst[i] = rst[i]+rst[j]
        rst[j] = rst[i]-rst[j]
        rst[i] = rst[i]-rst[j]
        i++
        j--
    }
    return string(rst)
}