今天看題的時(shí)候，遇到一個(gè)替換空格的題目，分析一下哈。

題目要求：把字符串中的每個(gè)空格替換成“%20”。例如輸入“we are happy”，則輸出“we%20are%20happy”。

解題思路：我們首先想到的是：移位思想。遇到空格就將空格后的所有字符后移兩位，然后填充空格為%20。

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

#pragma once #include<assert.h> #include<string.h>char* StrReplace(char* str,size_t length) {assert(str && length > 0);char *p = str;char *p1 = str;size_t len = strlen(str)+1;size_t i = len;while(p){while(*p != ' '){p++;if(*p == '\0'){return str;}}while((p1+i) != p){*(p1+i+1) = *(p1+i-1);i--;}len+=2;i = len;*p = '%';*(p+1) = '2';*(p+2) = '0';p+=2;}return str; }void Test() {char str[20] = "we are happy";cout<<StrReplace(str,20)<<endl; }

但是，我們?cè)倏纯此臅r(shí)間復(fù)雜度哈。顯然，每次移位操作都是O（N）,這樣經(jīng)過(guò)多次移位，使它的時(shí)間復(fù)雜度就變?yōu)镺（N^2）。這樣的效率實(shí)在有點(diǎn)低。我們?nèi)绾翁岣咚臅r(shí)間復(fù)雜度呢？

思路2：我們可以用計(jì)數(shù)的方式，統(tǒng)計(jì)字符串中總共的空格數(shù)，然后從后向前移位，使用兩個(gè)指針，p1指向字符串開始的位置，p2指向字符串尾部，移位將p2移動(dòng)2*空格個(gè)數(shù)位，遇到空格后填充，直到兩指針相遇，才停止移位。如圖所示（移位過(guò)程）：

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

#pragma once #include<assert.h> #include<string.h> char* StrReplace(char* str,size_t length) {assert(str && length > 0);char *p = str;char *p1 = NULL;char *p2 = NULL;size_t len = strlen(str);int count = 0;//統(tǒng)計(jì)空格數(shù)while(*p != '\0'){if(*p == ' ')count++;p++;}count*=2;p1 = str+len; //指向字符串尾p2 = str+len+count; //指向修改后字符串正確的位置while(p1 != p2){if(*p1 == ' '){p2 -= 2;*p2 = '%';*(p2+1) = '2';*(p2+2) = '0';if(p1 != p) //如果p1沒(méi)有到字符串頭時(shí)再減，防止越界{p1--;p2--;}}else //不是空格則直接后移{*p2 = *p1;p1--;p2--;}}return str; }void Test() {char str[20] = "we are happy";cout<<StrReplace(str,20)<<endl;char str1[20] = " are happy";cout<<StrReplace(str1,20)<<endl; }

執(zhí)行結(jié)果：

總結(jié)

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

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