题目描述请实现一个函数，将一个字符串中的每个空格更换成“%20”。例如，当字符串为We Are Happy.则经由更换之后的字符串为We%20Are%20Happy。
import java.util.;public class Solution { public String replaceSpace(StringBuffer str) { String str1 = str.toString(); str1 = str1.replace(" ","%20");// Java中的字符串更换函数。 return new String(str1); }}
口试算法解析
数据构造助教说：口试时候可千万不能这么写，就算是要用，只管即便还是把库函数自己手动实现一遍。口试官实在便是想考你怎么实现这个replace函数，结果你倒好，直接用了库函数，怪不得口试官夸你是个天才！
而且就算你这样用了库函数实现，你的这个算法的韶光繁芜度是 O(nn)。
首先更换第一个空格，变成“I%20am sad”,如下图所示。
可以看到am 和 sad 中的每个字符都今后移动了2次。紧接着更换第二个空格，得到下面的结果。
可以看到，sad中的每个字符又向后移动了两次！
假设字符串的长度为n,对付每个空格字符，须要移动后面的O(n)个字符（这里要把稳O(n)是一个近似即是，空格后面最大的字符串长度肯定是小于n的,比如说“I am sad”第一个空格后面的“am sad”长度肯定小于“I am sad”的字符串长度，我们这里取近似即是n）。如果有O(n)个空格字符，那么也便是说韶光效率是O（nn）。
优化算法思路
我们可以先遍历一次字符串，这样就可以统计出字符串空格的总数，并可以由此打算出更换之后的字符串的总长度。每更换一个空格，长度增加2，因此更换往后字符串的长度即是原来的长度加上2乘以空格数目。以"I am sad"为例，"I am sad"这个字符串的长度为8，里面有两个空格，因此更换之后字符串的长度是12。
长度12的新数组
我们从字符串的末端的后面开始复制和更换。准备两个指针A和指针B，指针A指向原字符串的末端，指针B指向新字符串的末端。
接下来我们向前移动指针A，在没碰着空格前,逐个把A指向的字符复制到指针B指向的位置。
接下来A往前，碰到了第一个空格：
碰到空格后，A往前移动一个，在B之前插入%、2、0三个字符。由于“%20”是三个字符，以是B向前移动三格。
同理,接下来我们向前移动指针A，在没碰着空格前,逐个把A指向的字符复制到指针B指向的位置。
A接下来向前移动碰到空格。
同理，A往前移动一个，在B之前插入%、2、0三个字符。由于“%20”是三个字符，以是B向前移动三格。
末了，将A的字符复制到B，结束。
Javaimportjava.util.;publicclassSolution{publicStringreplaceSpace(StringBufferstr){Stringstr1=str.toString();if(str1.equals(""))returnstr1;char[]strArray=str1.toCharArray();inti=0;intlengthSpace=0;while(i<strArray.length){if(strArray[i]=='')lengthSpace++;//打算空格数目i++;}intnewStrLength=strArray.length+lengthSpace2;//打算更换后的字符串长度char[]newStr=newchar[newStrLength];intj=newStrLength-1;i=strArray.length-1;while(i>=0){if(strArray[i]!='')//如果没遇见空格，直接复制，并向前移动{newStr[j--]=strArray[i--];}else{//如果遇见空格了，新字符串前加三个字符%20newStr[j--]='0';//然后新字符串往前移动3格，老字符串移动一格。newStr[j--]='2';newStr[j--]='%';i--;}}returnnewString(newStr);}}C++
classSolution{public:voidreplaceSpace(charstr,intlength){//遍历一边字符串找出空格的数量if(str==NULL||length<0)return;inti=0;intoldnumber=0;//记录以前的长度intreplacenumber=0;//记录空格的数量while(str[i]!='\0'){oldnumber++;if(str[i]==''){replacenumber++;}i++;}intnewlength=oldnumber+replacenumber2;//插入后的长度if(newlength>length)//如果打算后的长度大于总长度就无法插入return;intpOldlength=oldnumber;//把稳不要减一由于隐蔽个‘\0’也要算里intpNewlength=newlength;while(pOldlength>=0&&pNewlength>pOldlength)//放字符{if(str[pOldlength]=='')//碰到空格就更换{str[pNewlength--]='0';str[pNewlength--]='2';str[pNewlength--]='%';}else//不是空格就把pOldlength指向的字符装入pNewlength指向的位置{str[pNewlength--]=str[pOldlength];}pOldlength--;//不管是if还是elsr都要把pOldlength前移}}};Python
#--coding:utf-8--classSolution:#s源字符串defreplaceSpace(self,s):#writecodehereif(s==""):returnsstrArray=list(s)i=0;lengthSpace=0;while(i<len(strArray)):if(strArray[i]==''):lengthSpace+=1i+=1;newStrLength=len(strArray)+lengthSpace2;newStr=newStrLength['']j=newStrLength-1;i=len(strArray)-1;while(i>=0):if(strArray[i]!=''):newStr[j]=strArray[i];i-=1j-=1else:newStr[j]='0';j-=1newStr[j]='2';j-=1newStr[j]='%';j-=1i-=1newStr=''.join(newStr)returnnewStrJS
functionreplaceSpace(str){if(str=="")returnstr;varstrArray=str.split('');vari=0;varlengthSpace=0;while(i<strArray.length){if(strArray[i]=='')lengthSpace++;i++;}varnewStrLength=strArray.length+lengthSpace2;varnewStr=[];for(i=0;i<newStrLength;i++){newStr[i]='';}varj=newStrLength-1;i=strArray.length-1;while(i>=0){if(strArray[i]!=''){newStr[j--]=strArray[i--];}else{newStr[j--]='0';newStr[j--]='2';newStr[j--]='%';i--;}}returnnewStr.join('');}Php
<?phpfunctionreplaceSpace($str){if($str=="")return$str;$strArray=str_split($str);$i=0;$lengthSpace=0;while($i<count($strArray)){if($strArray[$i]=='')$lengthSpace++;$i++;}$newStrLength=count($strArray)+$lengthSpace2;$newStr=array();array_pad($newStr,$newStrLength,'');$j=$newStrLength-1;$i=count($strArray)-1;while($i>=0){if($strArray[$i]!=''){$newStr[$j--]=$strArray[$i--];}else{$newStr[$j--]='0';$newStr[$j--]='2';$newStr[$j--]='%';$i--;}}//return$newStr[0];$i=0;$result='';while($i<$newStrLength){$result.=$newStr[$i++];}return$result;}动画展示
絮叨
你的在看和转发便是我原创文章的不竭动力！
感激大家！
。
