【剑指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();
    }
}

方法三、双指针法
image.png
image.png
需要将上面的字符串转化为下面的字符串。
首先观察两者的区别,新字符串比旧字符串多2个字符,换句话说,旧字符串每多一个空格,新字符串多一组‘%20’也就是新字符串多两个字符。那么依此规则使用Java的setLength规则扩大旧字符串。例子中将10扩大成12.然后设置两个指针。
此时旧字符串经过扩充近似可以看成:
image.png
指针1从旧字符串最后一位10开始,指针2从新字符串最后一位12开始,遍历直到指针1走到头。
当指针1指向的是非空格,例如‘d’,此时指针1指向位置10,字符‘d’,将‘d’直接插入到指针2的指向,也就是12.再将新旧指针同步左移一位。以此类推,直到指针1指向空格,此时指针1指向位置5,新指针指向位置7。
image.png
也就是这个样子,这个时候在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();

    }
}

以上