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