请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解析：
最笨的方法就是从前往后遍历，当遇到一个空格时就做替换，由于替换后1个字符就会变成3个字符，那么必须将空格后面的所有字符都后移两个字节，否则就有两个字符被覆盖。如此操作的时间复杂度为O（n^2）。这里就不给出该过程的代码了。

最好的方法应该是从后遍历实现，这样就可以在O(n)时间内完成替换工作了。下面给出代码：

1. class Solution {
   
2. public:
   
3.     //length为给字符串分配的空间长度
   
4.         void replaceSpace(char* str,int length) {
   
5.         if(str == NULL|| length <= 0){
   
6.             return;
   
7.         }
   
8.         
   
9.         //统计字符串长度和空格数
   
10.         int originalLen = 0;
    
11.         int spaceNum = 0;
    
12.         int i = 0;
    
13.         while(str[i] != '\0'){
    
14.             ++originalLen;
    
15.             if(str[i] == ' '){
    
16.                 ++spaceNum;
    
17.             }
    
18.             i++;
    
19.         }
    
20.         
    
21.         //计算替换后字符串长度
    
22.         int newLen = originalLen + 2 * spaceNum;
    
23.         if(newLen > length){
    
24.             return;
    
25.         }
    
26.         
    
27.         //从后往前替换空格操作
    
28.         int indexOfOriginal = originalLen;
    
29.         int indexOfNew = newLen;
    
30.         while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal){
    
31.             if(str[indexOfOriginal] == ' '){
    
32.                 str[indexOfNew--] = '0';
    
33.                 str[indexOfNew--] = '2';
    
34.                 str[indexOfNew--] = '%';
    
35.             }else{
    
36.                 str[indexOfNew--] = str[indexOfOriginal];
    
37.             }
    
38.             --indexOfOriginal;
    
39.         }
    
40.         }
    
41. };

复制代码

以上给出了C代码的过程，因为在Java中已经已经为字符串提供了对应的方法，但是我们也应该对其进行实现过程进行了解。下面给出String源码中两个replace方法的源码实现：
public String replace(char oldChar, char newChar) {
        if (oldChar != newChar) {
            int len = value.length;
            int i = -1;
            char[] val = value; /* avoid getfield opcode */

            while (++i < len) {
                if (val[i] == oldChar) {
                    break;
                }
            }
            if (i < len) {
                char buf[] = new char[len];
                for (int j = 0; j < i; j++) {
                    buf[j] = val[j];
                }
                while (i < len) {
                    char c = val[i];
                    buf[i] = (c == oldChar) ? newChar : c;
                    i++;
                }
                return new String(buf, true);
            }
        }
        return this;
    }


public String replace(CharSequence target, CharSequence replacement) {
        return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
                this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}