[LeetCode]38.报数——题解(执行用时击败91% ,内存消耗击败 97%)
[LeetCode]38.报数——题解(执行用时击败91% ,内存消耗击败 97%)
1.题目描述
报数序列是一个整数序列，按照其中整数的顺序报数，得到下一个数。前五项如下： 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"
2.分析
首先可以看到每一个报数的整数序列（字符串）是在“Count and Say”上一个报数的整数序列，即记数上一个报数结果中每个数字出现的次数。比如n=3时，整数序列是21，是由“1个2和1个1”组成，因此当下一个报数时（n=4），报数的整数序列位1211.
所以，抓住“每一个报数的整数序列（字符串）是在“Count and Say”上一个报数的整数序列”，我们可以用上一个整数序列推算下一个整数序列，代码中永远只更新相邻两个报数的整数序列，而不需要保存多个或者全部。显而易见，我们需要从第一个报数者推算。
另一个问题是如何"Count and Say":
- Count: 计数每个数字出现的次数
- Say：保存当前统计的是哪个数字
- 每个新数字出现的位置init
比如1211：
开始时统计的数字是1，开始统计的位置init是0，下一个数字2不等于1，因此count为1，整数序列为11。此时count清零，因为要下一个数字需要重新开始统计。当前统计的数字是2，开始统计的位置init是1，下一个数字1不等于2，因此count为1，整数序列为1112。同样，count清零，init更新为2，因为下一个新数字1出现的位置是2.按照上述思路，直至统计完整个证书序列。
3.代码
string countAndSay(int n) {
if (n == 1){
return "1";
}
//存储每个报数的结果
string curRes = "";
//存储上次报数的结果
string lastRes = "1";
//报数计数变量
int i = 1;
//上一次报数结果的计数变量
int j = 0;
//报数结果中每个新的数字出现的位置，比如1211，init分别为0，1，2
int init = 0;
//每个新数字的个数，比如1211，count分别为1，1，2
int count = 0;
//上一个报数结果的长度，比如1211，length为4
int length = lastRes.length();
while (i <= n){
while (j<length){
if (lastRes[j] == lastRes[init]){
count++;
j++;
}
else{//出现新数字，记录上一个数字的统计结果和新数字的位置init
curRes.append(1, char(count + '0'));
curRes.append(1, char(lastRes[j - 1]));
count = 0;
init = j;
}
}
curRes.append(1, char(count + '0'));
curRes.append(1, char(lastRes[j - 1]));
i++;
if (i >= n){
return curRes;
}
length = curRes.length();
lastRes = curRes;
curRes = "";
j = 0;
count = 0;
init = 0;
}
return curRes;
}4.执行结果
