问题描述：请实现一个函数，把字符串中的每个空格替换成”%20“。

例如：

输入：“We are happy.”

输出：”We%20are%20happy.”

思路1：按顺序找出空格所在的位置（下标），然后利用字串相加，将去除空格的字串用“%20”连接起来

/**

     * 面试题4：替换空格

     * @param str

     * @return

     */

    public static String replaceSpace(StringBuffer str){

        String s = "";

        int start = 0;

        while(start >= 0){

            int begin = start;

            start = str.indexOf(" ", start);

            if(start >= 0){

                s = s + str.substring(begin, start) + "%20";

                start++;

            }else{

                s = s + str.substring(begin, str.length());

                break;

            }

        }

        return s;

    }

思路2：按照一般的想法，我们遍历字符，每遇到空格就将之替换，但是需要后面的字符的移动，这样做需要的移动次数很多。O（n^2)

思路3：基于思路2,我们移动的时候从后开始，这样就会减少很多重复的元素移动。

public static String replaceBlank(StringBuffer str){

        if(str == null || str.length() < 0){

            return null;

        }

        int olength = str.length();

        int nblank = 0;

        for(int i = 0; i < olength; i++){

            if(str.charAt(i) == ' '){

                nblank++;

            }

        }

        int newLength = olength + 2 * nblank;

        int increas = 2*nblank;

        while(increas > 0){//此处是为了增加容量，不知道怎么用别的方法了

            str.append(",");

            increas--;

        }

        System.out.println(str.length());

        int indexOforiginal = olength-1;

        int indexOfnew = newLength-1;

        while(indexOforiginal >= 0 && indexOfnew > indexOforiginal){

            if(str.charAt(indexOforiginal) == ' '){

                str.setCharAt(indexOfnew, '0');

                indexOfnew--;

                str.setCharAt(indexOfnew, '2');

                indexOfnew--;

                str.setCharAt(indexOfnew, '%');

                indexOfnew--;

            }else{

                str.setCharAt(indexOfnew, str.charAt(indexOforiginal));

                indexOfnew--;

            }

            indexOforiginal--;

        }

        return str.toString();

    }