字符串系列② -- 替换空格

• 题目
• 思路
• 代码实现
• • 方法二的实现
  • StringBuffer的实现方法
• 数组填充类算法问题的思考

此题对应LeetCode中剑指offer05

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = “We are happy.”
输出：“We%20are%20happy.”

在拿到字符串后，先计算空格数，再根据要替换的字符对数组进行扩容，使用双指针法，此后有两种处理方法：
方法一：创建一个新的扩容好的数组，一个指针（A指针）指着新数组的头部，另外一个指针（B指针）指着原数组的首部，然后依次添加，B指针依次向前，当指到空格时，A指针添加替换物。

方法二（更高效）：只创建一个数组，两个指针同时对这个数组作用，在讲s添加到数组中去后，A指针指向原s的尾端，而B指针指向数组的尾端，采取从尾部向头部添加的方式。添加过程同方法一！
为什么从尾部开始添加？：你可以假设从头部开始添加，会发现添加指针可能会比原内容指针跑得快，这就导致了有的原内容还没有被添加就被覆盖了，导致这部分原数据丢失！而从尾部添加，添加指针永远比原内容指针跑得慢，最多同步，不可能出现超过的情况，这就保证了数据的安全性。

public String solution1(String s){
        //先计算空格，创建计数器
        int count = 0;
        for(char kongge:s.toCharArray()){
            if(kongge == ' '){
                count++;
            }
        }
        //根据空格计算新建数组的长度
        char[] ss = new char[s.length()+count*2];
        //将原数组放入
        for(int i = 0;i < s.length();i++){
            ss[i] = s.charAt(i);
        }
        //建立指针
        int add = ss.length - 1;
        //添加原内容指针与for循环合并
        for(int content = s.length() - 1;content >= 0;content--){
            if(ss[content] == ' '){
                ss[add] = '0';
                ss[add-1] = '2';
                ss[add-2] = '%';
                add-=3;
            }else{
                ss[add] = ss[content];
                add--;
            }
        }
        return new String(ss);
    }

public static String replaceSpace(StringBuffer str) {
        if (str == null) {
            return null;
        }
		//选用 StringBuilder 单线程使用，比较快，选不选都行
        StringBuilder sb = new StringBuilder();
		//使用 sb 逐个复制 str ，碰到空格则替换，否则直接复制
        for (int i = 0; i < str.length(); i++) {
		//str.charAt(i) 为 char 类型，为了比较需要将其转为和 " " 相同的字符串类型
        //if (" ".equals(String.valueOf(str.charAt(i)))){
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }

其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

原因如下：

• 不同再次创建新的数组，可以直接在扩容的数组上进行操作
• 若从前向后填充数组，会对原数组数据覆盖而丢失，而从后往前覆盖则完美的避免了这个问题（未添加部分永远不会被提前覆盖）！