面试题2：替换空格

来源：《剑指Offer》 题目：请实现一个函数，把字符串的每个空格替换成”%20”，原字符串后面有足够的空间，要求在原字符串上操作。例如输入”we are happy”，则输出”we%20are%20happy”。 分析：先遍历一遍统计出空格数，一个空格替换成三个字符，长度增

来源：《剑指Offer》

题目：请实现一个函数，把字符串的每个空格替换成”%20”，原字符串后面有足够的空间，要求在原字符串上操作。例如输入”we are happy”，则输出”we%20are%20happy”。

分析：先遍历一遍统计出空格数，一个空格替换成三个字符，长度增加了2，N个空格，长度增加2N。则
替换后的字符串长度 = 原字符串长度 + 2N
设置两个指针，一个指向原字符串末尾，一个指向新字符串末尾。第二遍遍历，从后往前遍历。将原字符串最后一个字符复制到新字符串最后一个字符的位置，两个指针同时前移。当原字符串遇到空格，在新字符串对应位置插入”%20”三个字符，接着原字符串指针前移1位，新字符串指针前移3位。如此操作，直到原字符串第一个字符也复制完结束。

代码（C++）：

<code><span>#include<iostream></iostream></span>
<span>using</span> <span>namespace</span> <span>std</span>;

<span>#define MAX_LEN 100</span>

<span>/*
    函数功能：替换字符串中的空格
  */</span>
<span>void</span> replaceBlank(<span>char</span> data[])
{
    <span>int</span> i=<span>0</span>,j;
    <span>int</span> old_len;
    <span>int</span> new_len;
    <span>int</span> blank_num=<span>0</span>;
    <span>// 遍历一遍，找出空格数</span>
    <span>while</span>(data[i]!=<span>'\0'</span>)
    {
        <span>if</span>(data[i]==<span>' '</span>)
        {
            blank_num++;
        }
        i++;
    }
    <span>//-----------这里是关键------------</span>

    <span>// 原来字符串长度</span>
    old_len=i+<span>1</span>;
    <span>// 计算新字符串长度</span>
    new_len=old_len+<span>2</span>*blank_num;
    <span>// 重置i，j</span>
    i=old_len-<span>1</span>;
    j=new_len - <span>1</span>;

    <span>//-----------这里是关键------------</span>


    <span>// 再遍历一遍，替换空格</span>
    <span>while</span>(i>=<span>0</span>)
    {
        <span>if</span>(data[i]!=<span>' '</span>)
        {
            data[j]=data[i];        
            j--;
        }
        <span>else</span>
        {
            data[j]=<span>'0'</span>;
            data[j-<span>1</span>]=<span>'2'</span>;
            data[j-<span>2</span>]=<span>'%'</span>;
            j-=<span>3</span>;
        }
        i--;
    }

}
<span>int</span> main()
{
    <span>char</span> str[MAX_LEN];<span>// 声明一个字符数组</span>

    <span>// 输入数组</span>
    <span>cout</span>"请输入一个字符串，不超过20个字符"// 替换
    replaceBlank(str);
    <span>// 打印</span>
    <span>cout</span>return <span>0</span>;
}

</code>