替换空格

题目描述:请实现一个函数，把字符串中的每个空格替换成"%20"。

样例输入:"We are happy."
样例输出："We%20are%20happy."
说明：假设输入的字符串有足够的内存空间，可以装下替换后的新字符串，请在原串的基础上进行替换。

解题思路:

这一题很容易想到从头到尾遍历，然后替换空格。但由于一个空格替换成三个字符，我们必须把空格之后的字符向后移动两位。这样一来时间复杂度即为O(n^2).不是很好的解法。合理的做法是，先遍历一遍字符串，统计出空格的数量，然后算出把空格替换成‘%20’之后的新的字符串的长度。使用两个指针，一个指向原来字符串的末尾，另一个指向替换之后的字符串的末尾。遇到普通字符就把字符放到新的串上，两个指针分别向前走一步，遇到空格原字符串的指针向前走一步新的向前走三步，并替换成'%20'.如此一来便可在O(n)的时间复杂度之内完成。

话不多说，代码如下(C++):

//
//  main.cpp
//  replaceBlankSpace
//
//  Created by 孙艳东 on 2017/11/30.
//  Copyright © 2017年 孙艳东. All rights reserved.
//

/*
 *题目描述:请实现一个函数，把字符串中的每个空格替换成‘%20’。例如输入'We are happy.'
 *则输出'We%20are%20happy.'，假设原来输入字符串之后有足够多的内存。在原来的字符串上进行替换
 *
 *解题思路：先统计出有多少个空格，计算出替换后的长度，然后创建一个新的数组，用两个指针从后往前插入。
 *时间复杂度为O(n)
 */

#include <iostream>
using namespace std;

void replaceBank(char str[],int length) {
    if (str == NULL || length < 0) {
        return;
    }
    int originStrLength = 0;
    int newStrLength = 0;
    // 计算替换后的长度
    int i = 0;
    while (str[i] != '\0') { // 不是输入结束
        originStrLength ++;
        if (str[i] == ' ') {
            newStrLength ++;
        }
        i ++;
    }
    newStrLength = originStrLength + newStrLength * 2; // 替换后的实际长度
    
    int indexOfOrigin = originStrLength;
    int indexOfNew = newStrLength;
    while (indexOfOrigin >= 0 && indexOfNew > indexOfOrigin) {
        if (str[indexOfOrigin] == ' ') {
            str[indexOfNew --] = '0';
            str[indexOfNew --] = '2';
            str[indexOfNew --] = '%';
        }else {
            str[indexOfNew --] = str[indexOfOrigin];
        }
        indexOfOrigin --;
    }
}


int main(int argc, const char * argv[]) {
    char str[1024];
    cin.get(str, 1024);
    replaceBank(str, 1024);
    std::cout << str;
    return 0;
}