圖解劍指 offer 第二題：替換空格技术頭條網

圖解劍指 offer 第二題：替換空格

打算寫 圖解劍指 offer 66 題 的系列文章，不知道大家有沒有興趣~

題目描述

請實現一個函數，將一個字符串中的每個空格替換成 “%20” 。例如，當字符串為 We Are Happy 。則經過替換之後的字符串為 We%20Are%20Happy 。

題目解析

圖 1

這是一道很容易理解也很好簡單粗暴解決的問題。

對於很多編程語言而言，都內置了”替換“方法。只需要簡單的調用 API 即可。

比如：

return str.toString().replaceAll("\\s", "%20");

但，你有看過 replaceAll 的源碼實現麼。

return Pattern.compile(regex).matcher(this).replaceAll(replacement);
public String replaceAll(String replacement) {
 reset();
 boolean result = find();
 if (result) {
 StringBuilder sb = new StringBuilder();
 do {
 appendReplacement(sb, replacement);
 result = find();
 } while (result);
 appendTail(sb);
 return sb.toString();
 }
 return text.toString();
 }

即使你不懂 Java，看到關鍵字 regex，也能猜出這個源碼的實現使用了 正則表達式

，並且同時實現代碼裡面不停的創建與銷燬對象，性能方面很不理想。

對於此題，我們只需要去尋找可以被替換的部分，然後把不被替換的部分和替換者一個個連接起來就行了，遠遠不需要這麼複雜的操作。

解法

解法一：遇山開山,遇水架橋

題目要求我們將空格替換掉，那麼完全可以從前往後依次遍歷字符串，遇到空格替換即可。

動畫 2

使用這種解法在每一次碰到空格字符的時候都做替換，並且由於是把 1 個字符替換成 3 個字符，那麼每次替換一個空格後都需要把空格後面所有的字符都後移兩個字節，否則就有兩個字符被覆蓋。

假設字符串的長度是 n 。對每個空格字符，需要移動後面 O(n) 個字符，因此對含有 O(n) 個空格字符的字符串而言總的時間複雜度是 O(n^2) 。

解法二：山不轉水轉

通過指針（水）將字符（山）搬動。

首先遍歷一次字符串，統計出字符串中空格的總數，同時計算出替換之後的字符串的總長度。

以前面的字符串"We Are Happy."為例，"We Are Happy"這個字符串的長度是14（包括結尾符號'\0'），裡面有兩個空格，因此替換之後字符串的長度是 14 - 2 + 2 * 3 = 18 。

動畫 3

接下來就是 解法二 的精髓所在：從字符串的後面開始複製和替換。

首先，申請長度為 18 的空間。

圖 4

接下來，定義兩個指針：P1 和

P2 。

其中指針 P1 指向原始字符串的末尾，指針 P2 指向替換之後的字符串的末尾。

然後將指針 P1 向前移動，逐個把它指向的字符複製到指針 P2 指向的位置。

當碰到空格的時候，指針 P1 先不動，挪動指針 P2 的位置並賦值 %20 ，然後再同時向前移動並複製。

動畫 5

動畫 6

解法三：人造山

這種解法與 解法二 類似，唯一的不同點在於需要 重新開闢 一個新的數組進行數據的存放。

動畫 7

代碼如下：

//解題地址：https://www.nowcoder.com/ta/coding-interviews?query=&asc=true&order=&page=1
public class Solution {
 public String replaceSpace(StringBuffer str) {
 String str1 = str.toString();
 if(str1.equals(""))
 return str1;
 char [] strArray = str1.toCharArray();
 int i =0;
 int lengthSpace = 0;
 while(i < strArray.length){
 if(strArray[i] == ' ')
 lengthSpace++;
 i++;
 }
 int newStrLength = strArray.length + lengthSpace*2;
 char [] newStr = new char[newStrLength]; 

 int j = newStrLength-1;
 i = strArray.length - 1;
 while(i >= 0){
 if(strArray[i] != ' '){
 newStr[j--] = strArray[i--];
 }else{
 newStr[j--] = '0';
 newStr[j--] = '2';
 newStr[j--] = '%';
 i--;
 }
 }
 return new String(newStr);
 }
}