Heim  >  Fragen und Antworten  >  Hauptteil

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

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

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



}
伊谢尔伦伊谢尔伦2765 Tage vor622

Antworte allen(5)Ich werde antworten

  • 阿神

    阿神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

    Antwort
    0
  • PHP中文网

    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?。

    Antwort
    0
  • PHPz

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

    Antwort
    0
  • 天蓬老师

    天蓬老师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;
    }

    Antwort
    0
  • 迷茫

    迷茫2017-04-17 13:31:57

    正则匹配一个空格\s

    Antwort
    0
  • StornierenAntwort