问题描述
这个代码测试的时候超时，能帮忙分析一下原因么？九度检测最后一个测试用例超时。
/************************************************************************//* 请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 *//************************************************************************/#include <string>#include <iostream>using namespace std;int main(){ string s; getline(cin, s); size_t found = s.find(' '); while (found != string::npos) {s.replace(found, 1, '%20');found = s.find(' '); } cout << s;}
问题解答
回答1：你这个算法逻辑上是对的，但是时间复杂度是O(N^2)的，对于N > 10000的字符串就会超时。
可以改进成线性时间复杂度的算法。
我改了一下：
#include <string>#include <iostream>using namespace std;int main(){ string s; getline(cin, s); string res; for (int i = 0; i < s.size(); ++i) {if (s[i] == ’ ’) { res += '%20';}else { res.push_back(s[i]);} } cout << res << endl; return 0;}
http://ac.jobdu.com/problem.php?pid=1510 20ms AC
回答2：如果真的没有什么库函数的话..（最好还是用库函数）
#include <cstring>#include <climits>#include <iostream>#include <string>#include <cstdio>char* replace(const char *src){ /* 这个unsigned int相当于char[sizeof(int)] = {’%’, ’2’, ’0’, .......}; */ unsigned int magic = 0; magic += (unsigned char)’0’; magic <<= CHAR_BIT; magic += (unsigned char)’2’; magic <<= CHAR_BIT; magic += (unsigned char)’%’; // 最低CHAR_BIT位 size_t szall = std::strlen(src); // 字符串总长度 size_t szspace = 0; // 字符串中空格的个数 /* 下面这段代码主要完成空格计数功能 */ unsigned tailInt = ((unsigned int*)src)[szall / sizeof(int)]; size_t szValidCharInTail = szall % sizeof(int); // before: x .... x ? .... ? // after: 0 .... 0 x .... x tailInt >>= ((sizeof(int) - szValidCharInTail) * CHAR_BIT); while (tailInt != 0) {unsigned int ch = tailInt & 0xFF; // 这里假设每个字节8位if (ch == ’ ’) ++szspace;tailInt >>= CHAR_BIT; } for (size_t i = 0; i < szall / sizeof(int); ++i) {unsigned int v = ((unsigned int*)src)[i];while (v != 0){ unsigned int ch = v & 0xFF; // 这里假设每个字节8位 if (ch == ’ ’)++szspace; v >>= CHAR_BIT;} } char *result = new char[(szall - szspace) + szspace * 3 + 1]; size_t cur = 0; /* 下面这段代码主要完成空格替换功能 */ for (size_t i = 0; i < szall / sizeof(int); ++i) {unsigned int v = ((unsigned int*)src)[i];while (v != 0){ unsigned int ch = v & 0xFF; // 这里假设每个字节8位 if (ch == ’ ’) {unsigned int &v = *(unsigned int*)(&(result[cur]));v = magic;cur += 3; } else {result[cur++] = ch; } v >>= CHAR_BIT;} } tailInt = ((unsigned int*)src)[szall / sizeof(int)]; while (tailInt != 0) {unsigned int ch = tailInt & 0xFF; // 这里假设每个字节8位if (ch == ’ ’){ unsigned int &tailInt = *(unsigned int*)(&(result[cur])); tailInt = magic; cur += 3;}else{ result[cur++] = ch;}tailInt >>= CHAR_BIT; } result[cur] = 0; return result;}int main(){ std::string str; getline(std::cin, str); char *result = replace(str.c_str()); std::cout << result; delete result; return 0;}
上面的写法虽然长，看起来也费劲，但是性能较优；但一定不是最优的，因为strlen和空格的检测可以糅合到一起；另外，如果不确定src是四字节对齐的，应该对开头的几个不对齐字节做额外的检测。先计数主要避免了多次动态内存分配的开销，如果字符串不是大的离谱，因为缓存的原因，计数特别快；每次检测一个INT，对其做4次位检测是很快的，因为4次检测都在寄存器中进行。不过，这种优化也只是建议性的（也同时展示了C/C++的屌）；要真正的优化，还得各种细节，比如，把确定为4次的循环展开等..因此，尽最大的可能使用库，是你的最佳选择，我记得JAVA的String里就有个replace？。
回答3：你这样的复杂度太高了呢， 循环里面的s.find(' ')就已经是 O(n)的复杂度了，这个题可以一次遍历＋替换就可以完成的呀，就是循环一次，碰见一次空格 就替换掉就行了， 大致写了一下，你看看能不能过？
#include <string>#include <iostream>using namespace std;int main(){ string s; getline(cin, s); string t = s; int lenght = s.length(), r = 0; for(int i = 0; i < lenght; i++) {if(s[i] == ’ ’){ t.replace(i+2*r, 1, '%20'); r += 1;} } //size_t found = s.find(' '); //while (found != string::npos) //{ // s.replace(found, 1, '%20'); // found = s.find(' '); //} cout << t<<endl;}回答4：
题主的代码只需要修改一处就可以了：
#include <string>#include <iostream>using namespace std;int main(){ string s; getline(cin, s); size_t found = s.find(' '); while (found != string::npos) {s.replace(found, 1, '%20');found = s.find(' ', found); // <-- 每次查找，从上次停止的地方开始 } cout << s;}回答5：
正则匹配一个空格s
