劍指offer面試題

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

看到題目后的思路

看到這個(gè)題目后，我們首相應(yīng)該想到的是：原來(lái)的一個(gè)空格字符，經(jīng)過(guò)替換后就成了三個(gè)字符，因此字符會(huì)變長(zhǎng)，那么很有可能會(huì)覆蓋原來(lái)的字符。如果是在一個(gè)新創(chuàng)建的字符串上做替換，就可以有足夠的空間，顯然題目上沒(méi)有明顯的提出，那就應(yīng)該在原來(lái)的字符串上做替換

偽代碼實(shí)現(xiàn)

求出該字符串的長(zhǎng)度和字符串中含有的空格數(shù)

求出替換后的字符串的總長(zhǎng)度

準(zhǔn)備兩個(gè)指針pStr1，pStr2，pStr1指向原始字符串的末尾，pStr2指向替換后的字符串末尾

向前移動(dòng)pStr1和pStr2，逐個(gè)將pStr1指向的字符拷貝到Pr2指向的位置，知道遇到第一個(gè)空格為止

遇到空格后，將pStr1向前移動(dòng)一次，然后在pStr2之前插入“%20”，插入一個(gè)字符pStr2就要向前移動(dòng)一次

繼續(xù)向前移動(dòng)pStr1和pStr2，逐個(gè)將pStr1指向的字符拷貝到pStr2指向的位置，遇到空格繼續(xù)做“5”操作，直到pStr2和pStr1相等，說(shuō)明空格已經(jīng)全部替換完畢

思維圖

（圖片來(lái)源《劍指offer》）

c++代碼實(shí)現(xiàn)

class Solution { public:void replaceSpace(char *str, int length) {if (str == NULL && length <= 0)return;//如果是空直接返回int factlength = 0;//實(shí)際字符數(shù)int spacenumber = 0;//字符串中空格的數(shù)量int i = 0;while (str[i] != '\0'){++factlength;if (str[i] == ' '){++spacenumber;}++i;}//擴(kuò)展第二個(gè)字符串,//空格的數(shù)量*2是因?yàn)椤?20”一共三個(gè)字符，需要在原來(lái)每個(gè)空格的位置再加上兩個(gè)字符的長(zhǎng)度，才是第二個(gè)字符串的int newlength = factlength + spacenumber * 2;if (newlength > length){return;}//從后向前替換，這樣會(huì)減少替換的次數(shù)char *pStr1 = str + factlength;char *pStr2 = str + newlength;//如果pStr2 <= pStr1 了，說(shuō)明剩下的pStr2和pStr1的字符串相同了，也就沒(méi)有“ ”了，就不用替換了while (pStr2 > pStr1 && pStr1 >= 0){if (*pStr1 == ' '){*pStr2-- = '0';*pStr2-- = '2';*pStr2-- = '%';}else{*pStr2-- = *pStr1;}--pStr1;}return;} };

總結(jié)

以上是生活随笔為你收集整理的替换字符串中的空格的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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