劍指 Offer 05. 替換空格

難度簡單455

請實現(xiàn)一個函數(shù)，把字符串?s?中的每個空格替換成"%20"。

?

示例 1：

輸入：s = "We are happy."輸出："We%20are%20happy."

?

限制：

0 <= s 的長度 <= 10000

通過次數(shù)635,989提交次數(shù)843,510

第一種對法：

class?Solution?{

public:

????string?replaceSpace(string?s)?{

????????string?ans;

????????for(auto?a:s){

????????????if(a=='?'){

????????????????ans+="%20";

????????????}else{

????????????????ans+=a;

????????????}

????????}

????????return?ans;

????}

};

思路：

時間復(fù)雜度：O(n) 空間復(fù)雜度: O(n)

開一個新的字符串來存答案，當(dāng)檢測到是空格時將%20存到答案串中，不是空格時將字符存入到答案串中

第二種對法：

class?Solution?{

public:

????string?replaceSpace(string?s)?{

????????int?count?=?0;

????????int?sOldSize?=?s.size();

????????for(int?i=0;i<s.size();i++){

????????????if(s[i]=='?'){

????????????????count++;

????????????}

????????}

????????s.resize(s.size()+count*2);

????????int?sNewSize?=?s.size();

????????for(int?i?=?sNewSize?-?1,j?=?sOldSize?-?1;j?<?i;i--,j--){

????????????if(s[j]!='?'){

????????????????s[i]?=?s[j];

????????????}else{

????????????????s[i]?=?'0';

????????????????s[i-1]='2';

????????????????s[i-2]='%';

????????????????i-=2;

????????????}

????????}

????????return?s;

????}

};

思路：

雙指針法，時間復(fù)雜度 O(n)，空間復(fù)雜度O(1)

先數(shù)清楚字符串中有多少個空格，將原來的字符串resize成可以裝下答案字符串的長度

讓快指針指向倒數(shù)原串的末尾，讓慢指針指向新的字符串長度的末尾

快慢指針不斷往后移動

當(dāng)快指針指向的是字符時，就讓慢指針將指向的位置改成字符

當(dāng)快指針指向的是空格時，就讓慢指針將指向的位置與后兩個位置分別改成‘0’ ‘2’ ‘%’，然后慢指針-2迭代