替換空格

請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。

---

解題思路:

查找到所有空格的位置

將空格替換成相應(yīng)的字符串

---

提供API說明:

indexOf(String str ,int fromIndex):

• 參數(shù)：
  
  • str - 要搜索的子字符串。
  • fromIndex - 開始搜索的索引位置。
    返回：
    指定子字符串在此字符串中第一次出現(xiàn)處的索引，從指定的索引開始。

substring(index beginIndex ,int endIndex):

• 參數(shù)：
  
  • beginIndex - 起始索引（包括）。
  • endIndex - 結(jié)束索引（不包括）。
• 返回：
  
  • 指定的子字符串。
• 拋出：
  
  • IndexOutOfBoundsException - 如果 beginIndex 為負(fù)，或 endIndex 大于此 String 對象的長度，或 beginIndex 大于 endIndex。

---

代碼如下:

public class Solution {public String replaceSpace(StringBuffer str) {//所要的結(jié)果集String result = new String();//子串裁剪從0開始int start = 0;int end;//API的indexOf函數(shù),返回值給end//如果,end不是-1,則說明后面還可能存在空格字符//否則,說明此次start到字符末尾已經(jīng)沒有空格字符while((end=str.indexOf(" ", start))!=-1){//API的substring函數(shù),對返回值進行處理result = result + str.substring(start, end) + "%20";//start之前的部分已經(jīng)處理完畢,下次處理從end+1開始索引查找空格字符start = end+1;}//考慮邊界條件:需要加上最后一次沒有找到空格字符剩余的子串return result + str.substring(start);} }

---

在源字符串長度為n,替換字符串長度為m的情況下:
最壞空間復(fù)雜度為O(n*m)
如果indexOf()函數(shù)的復(fù)雜度總和為O(n),并且substring函數(shù)的復(fù)雜度為O(1)則:
最壞時間復(fù)雜度為O(n)
(以上如有錯誤,還望大神指教)

總結(jié)

以上是生活随笔為你收集整理的替换空格---剑指Offer的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。