面试现场
题目描述请实现一个函数，将一个字符串中的每个空格替换成“%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 < strArray.length) { if(strArray[i] == ' ') lengthSpace++;// 计算空格数目 i++; } int newStrLength = strArray.length + lengthSpace*2;//计算替换后的字符串长度 char [] newStr = new char[newStrLength]; int j = newStrLength-1; i = strArray.length - 1; 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 < 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) return newStr
function replaceSpace(str) { if(str == "") return str; var strArray = str.split(''); var i =0; var lengthSpace = 0; while(i < strArray.length) { if(strArray[i] == ' ') lengthSpace++; i++; } var newStrLength = strArray.length + lengthSpace*2; var newStr = []; for(i=0;i<newStrLength;i++) { newStr[i] =''; } var j = 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--; } } return newStr.join(''); }
Php
<?php function replaceSpace($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; }
动画展示
絮叨
你的在看和转发就是我原创文章的不竭动力！谢谢大家！。
