c++ - 将一个字符串中的空格替换成“%20”

Question

这个代码测试的时候超时，能帮忙分析一下原因么？九度检测最后一个测试用例超时。

/************************************************************************/
/* 请实现一个函数，将一个字符串中的空格替换成“%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;



}

Answer 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

Answer 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？。

Answer 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;


}

Answer 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;
}

Answer 5

正则匹配一个空格s