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

Your algorithm is logically correct, but the time complexity is O(N^2), and it will time out for N > 10000 strings.

An algorithm that can be improved to linear time complexity.

I changed it:

#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

If there is really no library function...(it is better to use library functions)

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

Although the above writing method is long and looks laborious, it has better performance; but it is definitely not optimal, because the detection of strlen and spaces can be combined; in addition, if you are not sure that src is four-byte aligned, Additional checks should be done on the first few misaligned bytes.
Counting first mainly avoids the overhead of multiple dynamic memory allocations. If the string is not outrageously large, counting is very fast due to caching; each time an INT is detected, it is very fast to do 4 bit checks on it. , because all 4 tests are performed in registers.
However, this kind of optimization is only a suggestion (it also shows the power of C/C++); for real optimization, various details are required, such as unrolling a loop determined to be 4 times, etc. Therefore , use the library as much as possible, it is your best choice. I remember that there is a replace in JAVA's String? .

Answer 3

The complexity of yours is too high. The s.find(" ") in the loop is already the complexity of O(n). This question can be completed by traversing + replacing once. It means looping once and encountering a space once. Just replace it, write it down roughly, see if you can pass it?

#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

The code of the questioner only needs to be modified in one place:

#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

Regular match a space s