一谎柄、題目
請(qǐng)編寫一個(gè)方法膏斤，輸入一個(gè)字符串彻舰，經(jīng)過一定的處理將字符串中的“空格”替換為“%20”并返回；
二诫咱、示例
輸入：
"hello world"
輸出：
"hello%20world"
三笙隙、解析
常規(guī)來說，這很簡單嘛坎缭，String的replaceAll秒解：
private static String replaceBlankByString(String string) {
return string.replaceAll("\\s", "%20");
}
這是依賴于String的正則替換竟痰，那么換個(gè)思路，自己實(shí)現(xiàn)幻锁；
新建一個(gè)單獨(dú)的list凯亮，作為替換后的字符數(shù)組集合（自動(dòng)擴(kuò)容），然后遍歷轉(zhuǎn)換后的字符數(shù)組哄尔，遇到“空格”字符即替換假消，代碼如下：
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();
}
可能很多人到這就已經(jīng)很滿意了，包括我自己也是岭接，但是網(wǎng)上卻有更優(yōu)解富拗，首先計(jì)算“空格”字符數(shù)量，得到最終生成的字符數(shù)組大小鸣戴，設(shè)置兩個(gè)指針啃沪，p1、p2窄锅，p1固定在原來字符串的尾部创千，p2固定在目前字符串的尾部，p1往前移動(dòng)入偷，移動(dòng)一格追驴，p2復(fù)制一個(gè)字符并也往前移動(dòng)一格，知道遇到“空格”字符疏之，p1往前移動(dòng)一格殿雪，p2往前移動(dòng)三格，并分別寫入'0'锋爪、‘2’丙曙、'%'三格字符，結(jié)束條件為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) {
// 計(jì)算空格數(shù)量
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);
}
看起來的確代碼最為復(fù)雜，但是細(xì)想想，這種方法只用一次遍歷纸兔，不用經(jīng)歷上面ArrayList的擴(kuò)容計(jì)算，因此效率應(yīng)該最高否副，采用replaceAll基于Java原生api汉矿，效率有待考證。
三备禀、效率
空口無憑洲拇，寫個(gè)小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));
}
先定個(gè)10,000個(gè)循環(huán)生成測(cè)試數(shù)據(jù)，觀察輸出：
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
通過數(shù)據(jù)對(duì)比很容易發(fā)現(xiàn)：
- 通過定長數(shù)組指針移動(dòng)計(jì)算效率最高另患，且非常穩(wěn)定纽乱；
-
String的replaceAll在數(shù)據(jù)量較小效率不如其他，數(shù)據(jù)量較大表現(xiàn)較好昆箕； - 采用list復(fù)制法數(shù)據(jù)量較小效率較好鸦列，數(shù)據(jù)量大了效率十分低下；
