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;



}

解决方案

你这个算法逻辑上是对的，但是时间复杂度是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

这篇关于c++ - 将一个字符串中的空格替换成“%20”的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！