38.报数

##一、题目原型：

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

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"

输入: 4
输出: "1211"

这题可能很多同学对于题目理解错了，我开始就是其中之一。
我将它误认为是2位2位为一组，其实是错误的。
再次分析题目后，我得到了正确的初步思路。

1	如果有相同的数字，count+1，直到有不同的数字，记录此时的count和当前数字，并将count重置为1

##三、解题思路：

/*
 1  ->      一个1 : 11
 11 ->      两个1 : 21
 21 ->      一个2一个1 : 12 11
 1211 ->    一个1 一个2 两个1 : 11 12 21
 111221 ->  三个1 两个2 一个1 : 31 22 11
 312211 ->  一个3 一个1 两个2 两个1 : 13112221
 13112221
 */

如果有相同的数字，count+1，直到有不同的数字，记录此时的count和当前数字，并将count重置

1
2
3


优点：理解简单
缺点：时间复杂度太高，循环嵌套较多

func countAndSay(_ n: Int) -> String {

var nums: String = "1"
if (n < 6) {
    if (n == 1) {
        return "1"
    }else if (n == 2) {
        return "11"
    }else if (n == 3) {
        return "21"
    }else if (n == 4) {
        return "1211"
    }else if (n == 5) {
        return "111221"
    }
}else {
    var j: Int = 1
    while j < n {

        var temp: String = ""
        var target: Int = Int(String.init(Array(nums)[0])) ?? 0
        var count: Int = 1;
        var i: Int = 1
        while i < nums.count {
            let int_num: Int = Int(String.init(Array(nums)[i])) ?? 0
            // 利用 当前数字target 和 第i个数字int_num 进行比对
            if (target != int_num)
            {
                // 如果不同数字，此时需拼接数据，count重置为1。
                temp.append(String.init(format: "%d%d", count, target))
                count = 1;
                target = int_num
                i = i + 1
            }else {
                // 相同数字，count++，继续。
                count = count + 1
                i = i + 1
            }
        }
        // 遍历完成，需要加上最后一组数据
        temp.append(String.init(format: "%d%d", count, target))
        nums = temp;
        j = j + 1
    }
}
return nums

}

1 2	```第二种办法：递归，利用数组存储

进阶思路：既然我们知道了相同数字count+1，否则保存数据。而且下一条数据是通过上一条数据得到的。我们想到了递归。
那么我们完全可以用数组将一组组数据保存起来，最后在拼接。

// 递归
// num：初始数组传[1]，之后传入的是haha()函数的返回值
// index：初始化为0，之后++；作用：控制递归范围。
// max：传入输入值n
func get_hahaArr(_ num: [Int],_ index: Int,_ max: Int) {
    
    if (index < max - 1) {
        get_hahaArr(haha(num), index+1, max)
        if (index == max - 2) {
            num_ = haha(num)
        }
    }
}

// 核心算法
// 其实和上面第一种方法（拼接字符串）是一样的道理，只是表现方式不同。
// 一个是拼接数字，一个是拼接数组里的元素。
func haha(_ nums: [Int]) -> [Int] {
    
    var i: Int = 1
    var count: Int = 1
    var repeatArr: [Int] = []
    
    // 将count和数字依次q存起来
    while i < nums.count {
        
        if (nums[i-1] == nums[i]) {
            count = count + 1
        }else {
            repeatArr.append(count)
            repeatArr.append(nums[i-1])
            count = 1
        }
        i = i + 1
    }
    repeatArr.append(count)
    repeatArr.append(nums[nums.count - 1])
    // print("\(nums),\(repeatArr)")
    return repeatArr
}

// 最终的拼接
// 通过n来取第几个数组
var num_: [Int] = []
func countAndSay(_ n: Int) -> String {
    
    guard (0<n && n <= 30) else { print("超出范围"); return "" }
    
    if (n == 1) {
        return "1"
    }else if (n >= 2) {
        get_hahaArr([1], 0, n)
        var str: String = ""
        for i in 0..<num_.count {
            str.append("\(num_[i])")
        }
        return str
    }
    return "n需要是正整数"
}

大家可以打开

```
// countAndSay(6)
[1],[1, 1]
[1, 1],[2, 1]
[2, 1],[1, 2, 1, 1]
[1, 2, 1, 1],[1, 1, 1, 2, 2, 1]
[1, 1, 1, 2, 2, 1],[3, 1, 2, 2, 1, 1]

#四、小结
1.耗时1844毫秒，内存消耗21.1M，超过5%的提交记录，总提交数18。
2.耗时12毫秒，内存消耗20.7M，超过96.2%的提交记录，总提交数18。