一、题目
请编写一个方法，输入一个字符串，经过一定的处理将字符串中的“空格”替换为“%20”并返回；
二、示例
输入：
"hello world"
输出：
"hello%20world"
三、解析
常规来说，这很简单嘛，String的replaceAll秒解：
private static String replaceBlankByString(String string) {
return string.replaceAll("\\s", "%20");
}
这是依赖于String的正则替换，那么换个思路，自己实现；
新建一个单独的list，作为替换后的字符数组集合（自动扩容），然后遍历转换后的字符数组，遇到“空格”字符即替换，代码如下：
private static String replaceBlankByList(String string) {
char[] arr = string.toCharArray();
// 注意泛型不能是基本类型
List<Character> list = new ArrayList<>();
for (char anArr : arr) {
if (anArr == ' ') {
list.add('%');
list.add('2');
list.add('0');
} else {
list.add(anArr);
}
}
StringBuilder builder = new StringBuilder();
for (Character c : list) {
builder.append(c);
}
return builder.toString();
}
可能很多人到这就已经很满意了，包括我自己也是，但是网上却有更优解，首先计算“空格”字符数量，得到最终生成的字符数组大小，设置两个指针，p1、p2，p1固定在原来字符串的尾部，p2固定在目前字符串的尾部，p1往前移动，移动一格，p2复制一个字符并也往前移动一格，知道遇到“空格”字符，p1往前移动一格，p2往前移动三格，并分别写入'0'、‘2’、'%'三格字符，结束条件为p1 、p2相遇；
可能文字不太有画面感，截取剑指Offer面试题：3.替换空格中的图片，更加清楚地阐述了这一过程；
示例图
我采用Java代码演示这一过程：
private static String replaceBlankByArray(String string) {
char[] arr = string.toCharArray();
int length = arr.length;
int blankCount = 0;
int newLength = 0;
for (Character c : arr) {
// 计算空格数量
if (c == ' ') {
blankCount++;
}
}
newLength = length + 2 * blankCount;
char[] newArr = new char[newLength];
System.arraycopy(arr, 0, newArr, 0, length);
for (int i = length - 1, j = newLength - 1; i != j; i--, j--) {
if (newArr[i] == ' ') {
newArr[j--] = '0';
newArr[j--] = '2';
newArr[j] = '%';
} else {
newArr[j] = newArr[i];
}
}
return String.valueOf(newArr);
}
看起来的确代码最为复杂，但是细想想，这种方法只用一次遍历，不用经历上面ArrayList的扩容计算，因此效率应该最高，采用replaceAll基于Java原生api，效率有待考证。
三、效率
空口无凭，写个小demo一试便知：
public static void main(String[] args) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 10000; i++) {
builder.append("A B ");
}
long s = System.currentTimeMillis();
replaceBlankByString(builder.toString());
System.out.println("replaceAll cost:" + (System.currentTimeMillis() - s));
s = System.currentTimeMillis();
replaceBlankByList(builder.toString());
System.out.println("list cost:" + (System.currentTimeMillis() - s));
s = System.currentTimeMillis();
replaceBlankByArray(builder.toString());
System.out.println("array cost:" + (System.currentTimeMillis() - s));
}
先定个10,000个循环生成测试数据，观察输出：
replaceAll cost: 158
list cost: 89
array cost: 7
增加至100,000；
replaceAll cost: 164
list cost: 90
array cost: 16
增加至1000,000；
replaceAll cost: 324
list cost: 1223
array cost: 52
增加至10,000,000；
replaceAll cost: 3193
list cost: 46829
array cost: 505
通过数据对比很容易发现：
- 通过定长数组指针移动计算效率最高，且非常稳定；
-
String的replaceAll在数据量较小效率不如其他，数据量较大表现较好； - 采用list复制法数据量较小效率较好，数据量大了效率十分低下；
