[剑指Offer]6.替换空格

题目

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路

我们首先想到的就是从前往后扫描，如果空格，就替换为%20，但是这样需要移动空格后的元素。

我们还有一种方法，首先遍历一遍字符串，统计出空格的个数，并可以由此计算出替换之后的字符串的长度。每替换一个空格，长度增加2，因此替换之后的字符串长度等于原来的长度加上2乘以空格的个数。即 替换后的字符串的长度 = 原字符串长度 + 空格数*2。

我们从字符串的后面开始复制和替换。我们首先准备两个指针，p1和p2。指针p1指向原字符串的末尾位置，另一个指针p2指向新字符串的末尾位置。接下来我们移动指针p1，逐个把他指向的字符复制到p2指向的位置，直到碰到一个空格为止。当碰到一个空格时，指针p1向前移动一个位置，在p2之前插入字符串”%20”，同时指针p2向前移动三个位置。

代码

/*---------------------------------------
*   日期：2015-07-19
*   作者：SJF0115
*   题目: 6.替换空格
*   结果：AC
*   来源：剑指Offer
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

class Solution {
public:
    void replaceSpace(char* str,int size) {
        if(str == nullptr || size <= 0){
            return;
        }//if
        // 统计空格个数
        int count = 0;
        for(int i = 0;i < size;++i){
            if(str[i] == ' '){
                ++count;
            }//if
        }//for
        int newSize = size + count * 2;
        if(newSize == size){
            return;
        }//if
        int index = size - 1;
        int i = newSize - 1;
        // 替换空格
        while(index >= 0){
            if(str[index] == ' '){
                str[i--] = '0';
                str[i--] = '2';
                str[i--] = '%';
            }//if
            else{
                str[i--] = str[index];
            }//else
            --index;
        }//while
        str[newSize] = '\0';
    }
};

int main(){
    Solution s;
    char str[100] = "hello world";
    int size = strlen(str);
    s.replaceSpace(str,size);
    cout<<str<<endl;
    return 0;
}