题目描述请实现一个函数，将一个字符串中的每个空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
import java.util.*;public class Solution { public String replaceSpace(StringBuffer str) { String str1 = str.toString(); str1 = str1.replace(" "," ");// Java中的字符串替换函数。 return new String(str1); }}
数据结构助教说：面试时候可千万不能这么写，就算是要用，尽量还是把库函数自己手动实现一遍。面试官其实就是想考你怎么实现这个replace函数，结果你倒好，直接用了库函数，怪不得面试官夸你是个天才！而且就算你这样用了库函数实现，你的这个算法的时间复杂度是 O(n*n)。
首先替换第一个空格，变成“I am sad”,如下图所示。
可以看到am 和 sad 中的每个字符都往后移动了2次。紧接着替换第二个空格，得到下面的结果。
可以看到，sad中的每个字符又向后移动了两次！
假设字符串的长度为n,对于每个空格字符，需要移动后面的O(n)个字符（这里要注意O(n)是一个近似等于，空格后面最大的字符串长度肯定是小于n的,比如说“I am sad”第一个空格后面的“am sad”长度肯定小于“I am sad”的字符串长度，我们这里取近似等于n）。如果有O(n)个空格字符，那么也就是说时间效率是O（n*n）。
我们可以先遍历一次字符串，这样就可以统计出字符串空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。以"I am sad"为例，"I am sad"这个字符串的长度为8，里面有两个空格，因此替换之后字符串的长度是12。
长度12的新数组
我们从字符串的末尾的后面开始复制和替换。准备两个指针A和指针B，指针A指向原字符串的末尾，指针B指向新字符串的末尾。
接下来我们向前移动指针A，在没遇到空格前,逐个把A指向的字符复制到指针B指向的位置。
接下来A往前，碰到了第一个空格：
碰到空格后，A往前移动一个，在B之前插入%、2、0三个字符。由于“ ”是三个字符，所以B向前移动三格。
同理,接下来我们向前移动指针A，在没遇到空格前,逐个把A指向的字符复制到指针B指向的位置。
A接下来向前移动碰到空格。
同理，A往前移动一个，在B之前插入%、2、0三个字符。由于“ ”是三个字符，所以B向前移动三格。
最后，将A的字符复制到B，结束。
importjava.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 lengthSpace*2;//计算替换后的字符串长度
char[]newStr=newchar[newStrLength];
intj=newStrLength-1;
i=strArray.length-1;
while(i>=0)
{
if(strArray[i]!='')//如果没碰见空格，直接复制，并向前移动
{
newStr[j--]=strArray[i--];
}else{//如果碰见空格了，新字符串前加三个字符
newStr[j--]='0';//然后新字符串往前移动3格，老字符串移动一格。
newStr[j--]='2';
newStr[j--]='%';
i--;
}
}
returnnewString(newStr);
}
}
classSolution{
public:
voidreplaceSpace(char*str,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 replacenumber*2;//插入后的长度
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前移
}
}
};
#-*-coding:utf-8-*-
classSolution:
#s源字符串
defreplaceSpace(self,s):
#writecodehere
if(s==""):
returns
strArray=list(s)
i=0;
lengthSpace=0;
while(i<len(strArray)):
if(strArray[i]==''):
lengthSpace =1
i =1;
newStrLength=len(strArray) lengthSpace*2;
newStr=newStrLength*['']
j=newStrLength-1;
i=len(strArray)-1;
while(i>=0):
if(strArray[i]!=''):
newStr[j]=strArray[i];
i-=1
j-=1
else:
newStr[j]='0';
j-=1
newStr[j]='2';
j-=1
newStr[j]='%';
j-=1
i-=1
newStr=''.join(newStr)
returnnewStr
functionreplaceSpace(str)
{
if(str=="")
returnstr;
varstrArray=str.split('');
vari=0;
varlengthSpace=0;
while(i<strArray.length)
{
if(strArray[i]=='')
lengthSpace ;
i ;
}
varnewStrLength=strArray.length lengthSpace*2;
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
functionreplaceSpace($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) $lengthSpace*2;
$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;
}
你的在看和转发就是我原创文章的不竭动力！谢谢大家！。
