一、题目原型：
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
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位为一组，其实是错误的。
再次分析题目后，我得到了正确的初步思路。
如果有相同的数字，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重置
第一种方法：字符串拼接
优点：理解简单
缺点：时间复杂度太高，循环嵌套较多
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
}
第二种办法：递归，利用数组存储
进阶思路：既然我们知道了相同数字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需要是正整数"
}
大家可以打开print("\(nums),\(repeatArr)")看看传入的数组，和输入的数组。
// 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。
