Heim > Fragen und Antworten > Hauptteil
这个代码测试的时候超时,能帮忙分析一下原因么?九度检测最后一个测试用例超时。
/************************************************************************/
/* 请实现一个函数,将一个字符串中的空格替换成“%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;
}
阿神2017-04-17 13:31:57
你这个算法逻辑上是对的,但是时间复杂度是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
PHP中文网2017-04-17 13:31:57
如果真的没有什么库函数的话..(最好还是用库函数)
#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?。
PHPz2017-04-17 13:31:57
你这样的复杂度太高了呢, 循环里面的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;
}
天蓬老师2017-04-17 13:31:57
题主的代码只需要修改一处就可以了:
#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;
}