4
要求
時間限制：1秒 空間限制：32768K
題目描述
請實作一個函式，將一個字串中的空格替換成“%20”，例如，當字串為We Are Happy.則經過替換之后的字串為We%20Are%20Happy.
解題思路
拿到題目之后，一般會首先想到從頭開始掃描這個字串，遇到空格就將后面所有的字符都向后移動兩格，再插入%20，雖然這個辦法可行，但是時間復雜度為O（n^2），每一個字符都會有多次移動
現在希望每個字符只移動一次，我們要用兩個指標P1和P2，P1指向字串的最后一個字符'\0',P2指向替換了空格后的字串尾部，每一個空格都會導致字串增長兩個字符
具體程序如下圖所示
?
代碼
class Solution
{
public:
void replaceSpace(char *str,int length)
{
if(str==NULL || length<=0)
return;
int endIndexOfOriStr = -1;
int endIndexOfNewStr = -1;
int curIndexOfOriStr = -1;
do
{
++curIndexOfOriStr;
++endIndexOfOriStr;
++endIndexOfNewStr;
if(str[curIndexOfOriStr] == ' ')
endIndexOfNewStr += 2;
}while(str[curIndexOfOriStr] != '\0');
if(endIndexOfNewStr>=length)
return;
while(endIndexOfOriStr >= 0 && endIndexOfOriStr < endIndexOfNewStr)
{
if(str[endIndexOfOriStr]==' ')
{
--endIndexOfOriStr;
str[endIndexOfNewStr--] = '0';
str[endIndexOfNewStr--] = '2';
str[endIndexOfNewStr--] = '%';
}
else
{
str[endIndexOfNewStr] = str[endIndexOfOriStr];
--endIndexOfOriStr;
--endIndexOfNewStr;
}
}
}
};
由于還要搬磚，沒有辦法一一回復私信把學習資料發給大家，我直接整理出來放在下面，覺得有幫助的話可以下載下來用于學習
鏈接：https://pan.baidu.com/s/1C-9TE9ES9xrySqW7PfpjyQ 提取碼：cqmd
感謝各位人才的點贊、收藏、關注
微信搜「三年游戲人」識訓一枚有情懷的游戲人，第一時間閱讀最新內容，獲取優質作業內推
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525946.html
標籤：其他
上一篇：代碼隨想錄演算法訓練營第八天|344、反轉字串|541、反轉字串Ⅱ|劍指Offer 05、替換空格|151.翻轉字串里的單詞|劍指Offer58-Ⅱ、左旋轉字串
下一篇：演算法題--從尾到頭列印鏈表