牛客网剑指offer02，替换空格。

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

时间限制：1秒 空间限制：32768K

首先我们从前往后遍历记录空格数目，从后往前插入‘%20’，从后往前的好处体现在:

如图所示：在从前向后遍历的过程得到了空格数count=2；如果我们要从前往后遍历加元素，那么第3-5要移动（count-1）*2个位置，7-11要移动count*2；相当于7-11移动了两次两个空格位置，如果从后向前遍历插入，就都只会移动一次，因为length会一直减减，直到为0；

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
w e   a r e   l u c  k y 
w e % 2 0 a r e % 2  0 l  u   c k  y

class Solution {
public:
	void replaceSpace(char *str,int length) {
        int count=0;
//从前向后遍历字符串，得出空格数目
     for(int i=0;i<length;i++)
     {
         if(str[i]==' ')
             count++;
     }
//从后向前循环，每遇到一个空格就添加三个元素，如果没有遇到就将当时点赋值给s[j+count*2]因为字符串长度已经变成了j+2*count;
        for(int j=length-1;j>=0;j--)
        {
            if(str[j]==' ')
            {
                count--;
                str[j+2*count]='%';
               str[j+2*count+1]='2';
               str[j+2*count+2]='0';
            }
            else
            {
                str[j+2*count]=str[j];
            }
                
        }
	}
};

这种方法很显然没有考虑到数组越界的 问题，因为传入的length最后变成了length+2*count，会导致溢出或者数组越界。

第二种方法是第一种的改良优化。

还是这个图：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
w e   a r e   l u c  k y 
w e % 2 0 a r e % 2  0 l  u   c k  y

首先我们通过从前往后遍历字符串求出字符串的原长度oldnumber,还有空格数目count，继而由第一种方法的逻辑得到新字符串的长度是newnumber=oldnumber+count*2;

再然后就是上面的逻辑了从后向前插入了。这个可以防止数组越界，通过判断newnumber和length的大小判断。

代码如下：

class Solution {
public:
	void replaceSpace(char *str,int length) {
//判空
        if(str==NULL||length<0)
            return;
//定义并初始化数据
            int i=0;
            int oldnumber=0;//原数据长度
            int count=0;//空格数
            while(str[i]!='\0')//从头开始遍历，while的好处是用不到字符串长度通过判断字符串最后一个字符'\0'来终止循环。
            {
                oldnumber++;
                if(str[i]==' ')
                    count++;
                i++;
            }
        int newnumber=oldnumber+2*count;//加入%20的新数据长度
        int newlength=newnumber;//我们要建立两个临时变量来进行下面数据操作，定义一个新的字符串长度
        int oldlength=oldnumber;//原来的长度
        if(newlength>length)//注意这个地方是防止数组越界，数据溢出。当新的长度大于传入的长度时终止循环。
            return;
        while(newlength>oldlength&&oldlength>=0)//从后向前插入，控制oldlength--；
            {
                if(str[oldlength]==' ')
                {
                    str[newlength--]='0';//注意这个是从后向前传入的%20也要反着
                    str[newlength--]='2';
                    str[newlength--]='%';
                }
                else
                {
                    str[newlength--]=str[oldlength];//如果没有空格就将这个数传给新的
                }
                    
                oldlength--;//为了循环继续，要--；
            }
        }
};