面试现场

题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%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(n*n)。

首先替换第一个空格，变成“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（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三个字符。由于“%20”是三个字符，所以B向前移动三格。

同理,接下来我们向前移动指针A，在没遇到空格前,逐个把A指向的字符复制到指针B指向的位置。

A接下来向前移动碰到空格。

同理，A往前移动一个，在B之前插入%、2、0三个字符。由于“%20”是三个字符，所以B向前移动三格。

最后，将A的字符复制到B，结束。

Java

import?java.util.*;
public?class?Solution?{
????public?String?replaceSpace(StringBuffer?str)?{
????????String?str1?=?str.toString();
????????if(str1.equals(""))
????????????return?str1;
????????char?[]?strArray?=?str1.toCharArray();
????????int?i?=0;
????????int?lengthSpace?=?0;
????????while(i?=?0)
????????{
????????????if(strArray[i]?!=??'?')?//如果没碰见空格，直接复制，并向前移动
????????????{
????????????????newStr[j--]?=?strArray[i--];
????????????}else{????????????????//如果碰见空格了，新字符串前加三个字符%20
????????????????newStr[j--]?=?'0';//然后新字符串往前移动3格，老字符串移动一格。
????????????????newStr[j--]?=?'2';
????????????????newStr[j--]?=?'%';
????????????????i--;
????????????}
????????}
????????return?new?String(newStr);
????}
}

C++

class?Solution?{
public:
void?replaceSpace(char?*str,int?length)?{
????????//遍历一边字符串找出空格的数量
????????if(str==NULL||length<0)
????????????return?;
????????int?i=0;
????????int?oldnumber=0;//记录以前的长度
????????int?replacenumber=0;//记录空格的数量
????????while(str[i]!='\0')
????????????{
???????????????oldnumber++;
???????????????if(str[i]=='?')
???????????????????{
?????????????????????replacenumber++;
???????????????????}
??????????????????i++;
????????????}
????????int?newlength=oldnumber+replacenumber*2;//插入后的长度
????????if(newlength>length)//如果计算后的长度大于总长度就无法插入
????????????return?;
????????int?pOldlength=oldnumber;?//注意不要减一因为隐藏个‘\0’也要算里
????????int?pNewlength=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?-*-
class?Solution:
????#?s?源字符串
????def?replaceSpace(self,?s):
????????#?write?code?here
????????if(s?==?""):
????????????return?s
????????strArray?=?list(s)
????????i?=?0;
????????lengthSpace?=?0;
????????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)
????????return?newStr

JS

function?replaceSpace(str)
{
????if(str?==?"")
????????return?str;
????var?strArray?=?str.split('');
????var?i?=0;
????var?lengthSpace?=?0;
????while(i?=?0)
????{
????????if(strArray[i]?!=??'?')
????????{
????????????newStr[j--]?=?strArray[i--];
????????}else{
????????????newStr[j--]?=?'0';
????????????newStr[j--]?=?'2';
????????????newStr[j--]?=?'%';
????????????i--;
????????}
????}
????return?newStr.join('');
}

Php

=?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?

动画展示

絮叨

你的在看和转发就是我原创文章的不竭动力！谢谢大家！。