剑指Offer——替换空格

题目链接

题目

函数接口

题解

该题的思路比较浅显，也容易实现。核心思路就是遍历StringBuffer的每个字符，遇到空格就进行替换。对于实现编码应该没有太多的优化空间。

本文在这里给出三种解决方式。

方法一

方法一最为简单，也是最容易想到和实现的。

1.声明一个String字符串，然后使用for循环+charAt(index)依次遍历传入的StringBuffer的每一个字符。

2.在每次循环中进行判断。如果当前字符为空格，那么就在字符串中连接一个“%20”；若当前字符不为空格，那么就将当前字符连接进去。

3.最后返回替换完成的String字符串。

下面给出基于这一思路的Java代码

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	String newstr = "";
	for(int i=0;i <str.length();i++){
            newstr += str.charAt(i)== ?"%20":str.charAt(i);
	}
	return newstr;
    }
}

注：步骤2中可以使用if-else语句，这里为了减少代码量使用了条件运算符。

方法二

显然方法一是正确的，同时由于String字符具有初始化空值（不是null）。所以即使StringBuffer长度为0，也一样能保证最后回传的字符串是非空的，保证了鲁棒性。

但需要注意的是方法一中进行字符连接时采用的是直接拼接，这就为程序运行带来了许多不必要的开销。

因为Java在运行期每次进行字符串拼接时，实际上是在底层创建了一个StirngBuilder，然后调用append方法进行拼接。

同时由于每次拼接都会new 一个StringBuilder，且只使用一次就废弃。当这个StringBuffer足够大时，就必然会在堆中开辟大量无用的内存空间。从而为JVM带来许多不必要的开销。

为了解决这个问题，就需要用另一个载体来存放newstr。本文中使用的StringBuffer，但其实单机情况下使用StringBuilder效率更高。但为了未来可能的扩展和复用，这里选用了线程安全的StringBuffer。

代码如下

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	StringBuffer newstr = new StringBuffer();
	for(int i=0;i <str.length();i++){
	    newstr.append(str.charAt(i)== ?"%20":str.charAt(i));
	}
	return newstr.toString();
    }
}

需要注意的是，因为牛客网提供的函数接口返回值为String，所以不能直接返回newstr，应当进行toString。

方法三

以上两种方法其实可以看作同一种方法。但在笔试时，大可以使用JDK提供的API。本文中使用了String类的replaceAll()方法进行替换。

代码如下

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

这里可以使用两种方法。在这里简单说明一下两种方法的区别。

replace()和replaceAll()的方法头如下：

public String (char oldChar, char newChar)

public String replaceAll(String regex,String replacement)

这两种方法都能完成字符串的All Replace，主要区别在于其参数。 replace的两个参数都可以为cha或CharSequence，CharSequence是字符串序列，实际上就是字符串。所以replace支持单个字符和字符串的替换。

而replaceAll的参数一是正则表达式，参数二是用于替换的字符串。也即将一个字符串中符合正则规则的串都替换为replacement参数所存的字符串。由于正则表达式的功能性更强，考虑到未来可能的扩展。所以本文中采用了replaceAll()方法。

最后，需要注意的是，这两种方法都不会改变源字符串，预期的字符串通过返回值返回。所以程序中最后return的应该是replaceAll()的返回值，而不是源字符串str。

以上三种方法是笔者目前想到的较为合理的方法，都能够通过测试。如果有其他更为优化的方法，欢迎在评论区分享。