題目
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)湖雹，把字符串中的每個(gè)空格都換成%20兔簇。例如：輸入"We are happy"塘装，則輸出“We%20are%20happy”
在網(wǎng)絡(luò)編程中蛇摸，如果URL參數(shù)中含有特殊字符备图，如空格、'#'等，則可能導(dǎo)致服務(wù)器端無法獲得正確的參數(shù)值揽涮。我們需要將這些特殊字符號(hào)轉(zhuǎn)換成為服務(wù)器可能識(shí)別的字符抠藕。轉(zhuǎn)換的規(guī)則是在'%'跟上ASCII碼的兩位16進(jìn)制的表示。比如空格的ASCII碼是32蒋困，即16進(jìn)制的0x20盾似，因此空格被替換為“%20”。再比如'#'的ASCII碼為35雪标，即16進(jìn)制的0x23零院，它在URL中被替換為"%23"
看到這個(gè)題目，我們首先應(yīng)該想到的是原來一個(gè)空格字符村刨，替換之后變成'%'告抄、'2'和'0'這3個(gè)字符，因此字符串會(huì)變長(zhǎng)烹困。如果是在原來的字符串上進(jìn)行替換玄妈，就有可能覆蓋修改在該字符串后面的內(nèi)存。如果是創(chuàng)建新的字符串并在新的字符串上進(jìn)行替換髓梅，那么我們可以自己分配足夠多的內(nèi)存拟蜻。
時(shí)間復(fù)雜度為O(n2)的解法
最直觀的做法是從頭到尾掃描字符串，每次碰到空格字符串的時(shí)候進(jìn)行替換枯饿。由于是把一個(gè)字符替換成3個(gè)字符酝锅，我們必須要把空格后面所有的字符都后移2字節(jié)，否則就有兩個(gè)字符被覆蓋了
舉個(gè)例子奢方，我們從頭到尾把"We are happy"中的每個(gè)空格替換成為"%20"搔扁。為了形象起見，我們可以用一個(gè)表格來表示字符串蟋字，表格中的每個(gè)格子表示一個(gè)字符稿蹲。如下圖
- （a）字符串"We are happy"
- （b）把字符串中的第一個(gè)空格替換成為'%20'，灰色背景表示需要移動(dòng)的字符
- （c）把字符串中的第二個(gè)空格替換成'%20'鹊奖，淺色背景表示需要移動(dòng)一次的字符苛聘，深灰色背景表示需要移動(dòng)兩次的字符
我們替換第一個(gè)空格，這個(gè)字符串變成圖中(b)的內(nèi)容忠聚，表格中灰色背景的格子表示需要進(jìn)行移動(dòng)的區(qū)域设哗。接著我們替換第二個(gè)空格，替換之后的內(nèi)容是圖中(c)的內(nèi)容两蟀。同時(shí)网梢，我們注意到深灰色背景標(biāo)注的"happy"部分被移動(dòng)了兩次
假設(shè)字符串的長(zhǎng)度是n，對(duì)每個(gè)空格字符赂毯，需要移動(dòng)后面O(n)格字符战虏，因此對(duì)于含有O(n)格空格字符的字符串而言拣宰，總的時(shí)間效率是O(n2)
時(shí)間度為O(n)的解法
我們可以先遍歷一次字符串，這樣就能統(tǒng)計(jì)出字符串中空格的字?jǐn)?shù)烦感，并可以由此計(jì)算出替換之后的字符串的總長(zhǎng)度徐裸。每替換一個(gè)空格，長(zhǎng)度增加2啸盏，因此替換以后字符串的長(zhǎng)度等于原來的長(zhǎng)度加上2乘以空格數(shù)目重贺。我們還是以前面的字符串"We are happy"為例。"We are happy"這個(gè)字符串的長(zhǎng)度為14（包括結(jié)尾字符'\0'）回懦，里面有兩個(gè)空格气笙，因此替換之后字符串的長(zhǎng)度是18
我們從字符串的后面開始復(fù)制和替換。
首先準(zhǔn)備兩個(gè)指針：p1和p2怯晕。p1指向原始字符串的末尾潜圃，而p2指向替換之后的字符串的末尾，如圖（a）所示舟茶。接下來我們向前移動(dòng)指針p1谭期，逐個(gè)把它指向的字符復(fù)制到p2指向的位置，直到碰到第一個(gè)空格為止吧凉。
此時(shí)字符串如圖（b）所示隧出，灰色背景的區(qū)域是進(jìn)行了字符復(fù)制（移動(dòng)）的區(qū)域。碰到第一個(gè)空格之后阀捅，把p1向前移動(dòng)1格胀瞪，在p2之前插入字符串"%20"。由于"%20"的長(zhǎng)度為3饲鄙，同時(shí)也要把p2向前移動(dòng)3格凄诞，如圖（c）
我們接著向前復(fù)制，直到碰到第二個(gè)空格忍级，如圖（d）所示帆谍，和上次一樣，我們?cè)侔裵1向前移動(dòng)1格轴咱，并把p2向前移動(dòng)3格插入“%20”汛蝙，如圖（e）所示。此時(shí)p1和p2指向同一位置嗦玖，表明所有空格都已經(jīng)替換完畢患雇。
從上面的分析我們可以看到跃脊，所有的字符都只復(fù)制（移動(dòng)）一次宇挫，因此這個(gè)算法的時(shí)間效率是O(n)，比第一個(gè)思路快
算法實(shí)現(xiàn)
//string為字符串 length是字符串的總長(zhǎng)度
void replaceBlank(char string[], int length)
{
if (string == nullptr || length < 0 ) // 字符串為空酪术，不進(jìn)行后續(xù)操作
return;
//originalLength為字符串string的實(shí)際長(zhǎng)度
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while (string[i] != '\0') { // 計(jì)算空格個(gè)數(shù)
++originalLength;
if (string[i] == ' ') // 判斷是否為空格
++numberOfBlank;
++i;
}
// newLength為把空格替換成為%20之后的長(zhǎng)度
int newLength = originalLength + numberOfBlank * 2;
if (newLength > length) return ; // 確保在字符數(shù)組所開辟的內(nèi)存范圍內(nèi)
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while (indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) { // 確保在字符串的有效范圍內(nèi)進(jìn)行遍歷
if (string[indexOfOriginal] == ' ') // 利用數(shù)組設(shè)置值和交換值
{
string[indexOfNew--] = '0';
string[indexOfNew--] = '2';
string[indexOfNew--] = '%';
} else {
string[indexOfNew--] = string[indexOfOriginal];
}
--indexOfOriginal;
}
}
相關(guān)題目
有兩個(gè)排序的數(shù)組A1和A2器瘪，內(nèi)存在A1的末尾有足夠多的空間容納A2翠储。請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把A2中的所有數(shù)字插入A1中橡疼，并且所有的數(shù)字是排序的援所。
和前面的題目一樣，很多人首先想到的辦法是在A1中從頭到尾復(fù)制數(shù)字欣除，但這樣就會(huì)出現(xiàn)多次復(fù)制一個(gè)數(shù)字的情況住拭，更好的辦法是從尾到頭比較A1和A2中的數(shù)字，并把較大的數(shù)字復(fù)制到A1中的合適位置。
void combineArray(int A1[], int A2[], int length1, int length2)
{
int newIndex=((length1--)+(length2--))-1; //兩個(gè)數(shù)組現(xiàn)有值的總個(gè)數(shù)，確定最后的位置
while (length1 >= 0 && length2 >= 0)
{
if (A1[length1] >= A2[length2]) //從后往前比較插入
A1[newIndex--] = A1[length1--];
else
A1[newIndex--] = A2[length2--];
}
while (length1 >= 0) //剩余的值
A1[newIndex--] = A1[length1--];
while (length2 >= 0)
A1[newIndex--] = A2[length2--];
}
總結(jié)
在合并兩個(gè)數(shù)組（包括字符串）時(shí)眯牧，如果從前往后復(fù)制每個(gè)數(shù)字（或字符串）則需要移動(dòng)數(shù)字（或字符）多次觅彰，那么我們可以考慮從后往前復(fù)制，這樣就能減少移動(dòng)的次數(shù)贾铝，從而提高效率。
參考
《劍指offer》
