问题描述
提交这道题的时候，第四个测试点提示运行超时，根据内存占用看，应该是输入的N较大，导致运行超时
问题分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| int main() {
char d;
string result[2];
int sum;
cin>>d>>sum;
result[1] = d;
for (int i = 1; i < sum; ++i) {
result[0] = result[1];
result[1] = "";
char current = result[0][0];
int num = 1;
for (int j = 0; j < result[0].size(); ++j) {
if (j + 1 < result[0].size() && result[0][j + 1] == current) {
++num;
}
else{
result[1] = result[1] + current + to_string(num);
if (j + 1 < result[0].size()){
current = result[0][j + 1];
num = 1;
}
}
}
}
cout<<result[1];
}
|
解决运行超时的方法无非就是降低时间复杂度或者优化语句。我当前解决方法的时间复杂度是O(n^2^)，也想不出在更低的时间复杂度下解决方法，所以只能通过优化语句来降低运行时间。
解决方法
百度发现有遇到相同问题的同学给出了相关解决方案。我在字符串拼接时用了result[1] = result[1] + current + to_string(num); 而博主给出的解决方案是用temp += x来替代原来的写法，可以提高运行速度。修改后所由测试点通过。
参考博客：https://blog.csdn.net/qq_42251120/article/details/107406026
