首页 > 代码库 > 替换空格--《剑指offer》

替换空格--《剑指offer》

如题所示,题目很简单,替换空格,将字符串中的空格替换为%20;

"we are happy”替换成“we%20are%20happy”

如果每当我们遇到一个空格就将字符串向后平移两位,这样复杂度就是O(n2)了,这样的方法是不可取的,按照作者的来说,offer已不足拿到了;

而当我们反向从字符串末尾开始遍历,复杂度仅为O(n),当然前提的是该字符串有足够空间,否则替换会失败。

了解到思想之后程序也就比较简单了,发现自己的与作者的写的也比较类似,就此贴上了...

//2014-5-17
//用%20替换空格
#include <iostream>

using namespace std;

const int length = 20;

void ReplaceBlank(char arr[])
{
    if(arr == NULL || length < 0)
        return;
    int orilen = 0;  //实际长度
    int countBla = 0;  //空格的个数
    for(int i = 0; arr[i] != ‘\0‘; i++)
    {
        orilen++;
        if(arr[i] == ‘ ‘)
            countBla++;
    }
    int newlen = orilen + countBla * 2; //每一个空格都会增加两个空间

    if(newlen > length)
        return;

    for(int i = orilen; newlen > i; i--)
    {
        if(arr[i] == ‘ ‘)
        {
            arr[newlen--] = ‘0‘;
            arr[newlen--] = ‘2‘;
            arr[newlen--] = ‘%‘;
        }
        else
            arr[newlen--] = arr[i];
    }

}

int main()
{
    char *arr = new char[length];
    cin.getline(arr, length);

    ReplaceBlank(arr);

    cout << arr << endl;
    return 0;
}


O(∩_∩)O欢迎指教...