1084 外观数列 (20 point(s)) (测试点四)

这题的处理跟前面这题比较相似 1078 字符串压缩与解压 (20 point(s))

题目没有明说,刚开始还以为只是单纯数有多少个数字然后输出 “数字 重复次数” 但后面看见前面出现 1 1 后面也出现 1 1 的时候就怀疑这个想法,并且想到了前面写过的这题,所以觉得应该是输出连续出现的字符及其次数。在稿纸上演算了一遍,算到第八项没有问题,就按照这个思路开始写了。

但是最后一个测试点超时了。当时想不出这种循环为什么会超时,最多是 O(n^2) 但是时间给的并不少,而且数据集不算大。所以直接参考了别人的分析。

参考文章

分析给出的是字符串 = + + 这样拼接的效率是极慢的,而应该以 += 会更快,当然要求更快应该用 append() 函数。还有更快的两个,但是目前看不到这个需要,有必要再回来看看。目前先记住 += 和 append() 即可。

C++中string的拼接


想起写的时候的一些问题。当时拼接的是字符,所以需要把数字转换成数字字符,但是当时忘记加 ‘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;
}

1084 外观数列 (20 point(s)) (测试点四)

上一篇:TeslaManage 3.0版本


下一篇:输人法简介