这题的处理跟前面这题比较相似 1078 字符串压缩与解压 (20 point(s))。
题目没有明说,刚开始还以为只是单纯数有多少个数字然后输出 “数字 重复次数” 但后面看见前面出现 1 1 后面也出现 1 1 的时候就怀疑这个想法,并且想到了前面写过的这题,所以觉得应该是输出连续出现的字符及其次数。在稿纸上演算了一遍,算到第八项没有问题,就按照这个思路开始写了。
但是最后一个测试点超时了。当时想不出这种循环为什么会超时,最多是 O(n^2) 但是时间给的并不少,而且数据集不算大。所以直接参考了别人的分析。
分析给出的是字符串 = + + 这样拼接的效率是极慢的,而应该以 += 会更快,当然要求更快应该用 append() 函数。还有更快的两个,但是目前看不到这个需要,有必要再回来看看。目前先记住 += 和 append() 即可。
想起写的时候的一些问题。当时拼接的是字符,所以需要把数字转换成数字字符,但是当时忘记加 ‘0‘ 了,调试了好一会。
还有二重循环里面的第二个循环变量 j 其目的是统计从 i 开始往后有多少个重复的字符,所以需要从 j = i 开始。当时初始化错误,令了 j = 0 又浪费了不少调试的时间。
for (j = i; j < s.length() && s[j] == s[i]; j++);
参考别人看到更简洁的写法,可以将统计重复字符单独一个循环,通过记录 j 后移的位置与 i 相减,就可以得到重复字符的个数。而没必要再开一个 cnt 变量来记录。
next += d[i] + to_string(cnt + 1);
还有把原来的字符串拼接的代码改成这个。因为 to_string() 返回的是 string 类型,所以可以将 d[i] 的字符先拼起来,再跟前面的 next 接起来。
#include <bits/stdc++.h>
using namespace std;
int main() {
string d;
int n;
cin >> d >> n;
while(--n){
string next = "";
// i保存当前字符
for(int i = 0; i < d.size(); i++){
int cnt = 0;
// j 比较前后字符是否相同并且统计相同量
for(int j = i; j < d.size(); j++){
if(d[j] == d[j+1]){
cnt++;
}
else{
next += (char)d[i];
next += (char)(cnt + 1 + ‘0‘);
i += cnt;
break;
}
}
}
// 下一项的字符串
d = next;
}
cout << d;
}