【剑指offer】2、替换空格

【剑指offer】Java实现之替换空格

题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，初始字符串为We Are Happy.经过替换之后的字符串为We%20Are%20Happy。
视频题解地址：https://www.bilibili.com/video/bv1nT4y1g771
思路：
方法一、直接调用Java的replace函数

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replace(" ", "%20");
    }
}

方法二、新建一个字符串
换句话说就是，遍历旧字符串，将非空格的直接加到新字符串尾部，当遇到空格时，将‘%20’加到新字符串尾部。虽然很通俗易懂，但是显然新建一个字符串占用了空间，可以更加优化。

import java.util.*;
public class Solution {
    public String replaceSpace(StringBuffer str) {
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)== ' '){
                sb.append("%20");
            }else{
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

方法三、双指针法


需要将上面的字符串转化为下面的字符串。
首先观察两者的区别，新字符串比旧字符串多2个字符，换句话说，旧字符串每多一个空格，新字符串多一组‘%20’也就是新字符串多两个字符。那么依此规则使用Java的setLength规则扩大旧字符串。例子中将10扩大成12.然后设置两个指针。
此时旧字符串经过扩充近似可以看成：

指针1从旧字符串最后一位10开始，指针2从新字符串最后一位12开始，遍历直到指针1走到头。
当指针1指向的是非空格，例如‘d’，此时指针1指向位置10，字符‘d’，将‘d’直接插入到指针2的指向，也就是12.再将新旧指针同步左移一位。以此类推，直到指针1指向空格，此时指针1指向位置5，新指针指向位置7。

也就是这个样子，这个时候在7的位置上填充‘0’，6的位置上填充‘2’，5的位置上填充‘%’就可以直接处理掉空格。接着再继续指针移动直到0的位置，遍历完成。输出。

import java.util.*;
public class Solution {
    public String replaceSpace(StringBuffer str) {
        int num=0;
        for (int i=0;i<str.length();i++){
            if (str.charAt(i)==' '){
                num++;
            }
        }
        int oldStringLength=str.length();
        int newStringLength=oldStringLength+2*num;
        str.setLength(newStringLength);
//扩大字符串
        int indexNew = newStringLength-1;
        int indexOld = oldStringLength-1;
//建立指针1和指针2
        while (indexOld>=0&&indexNew>indexOld){
            if (str.charAt(indexOld)==' '){
//当指向的为空格，同时插入02%
                str.setCharAt(indexNew--,'0');
                str.setCharAt(indexNew--,'2');
                str.setCharAt(indexNew--,'%');
            } else {
                str.setCharAt(indexNew--,str.charAt(indexOld));
//指向不为空格则插入指向的字符
            }
            indexOld--;
 //循环结束不要忘记移动指针1
        }
        return str.toString();

    }
}

以上