替换空格
题目描述：
请实现一个函数，把字符串中的每个空格替换成” ”。例如，输入“We are happy.”，则输出“We are happy.”。
算法思想
逐个扫描每个字符，若是空格，则将“ ”追加至结果字符串；否则将当前字符追加至结果字符串。若是限定只能在原来的字符串上进行操作呢？这个也容易。采用Java很容易实现。从前往后扫描，扫描至当前的字符串（实际是一个字符，用substring函数），若是空格，则将原来的字符串替换成当前字符串的前面字符串+“ ”+当前字符串的后面的字符串。
但若是指明要用C语言且限定在原来的字符串上（也就是不能申请O(n)的辅助空间）实现呢？
我们知道，C语言中，字符串是用字符数组保存的。若从头到尾扫描字符串，每次碰到空格字符的时候进行替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移2字节，否则就有两个字符被覆盖了。
假设字符串的长度为n。对每个空格字符，需要移动后面O(n)个字符，因此对于含有O(n)个空格字符的字符串而言，总的时间效率为O(n^2)。显然，这个时间复杂度有点高。之所以高是因为数组中的很多字符都移动了很多次，也就是因为第一个空格字符后面的字符都没有一次移动到最终位置。如何才能使第一个空格字符后面的字符一次就移动到最终位置呢？答案是从后往前替换。
先遍历一遍字符串，统计出空格总数，计算出替换后的字符串总长度。每替换一个空格，长度增加2，因此替换后字符串的长度等于原来的长度加上2乘以空格数目。
然后我们从字符串的后面开始复制和替换。首先准备两个指针：P1和P2。P1指向原始字符的末尾，P2指向替换之后的字符串的末尾。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置。若当前P1指向的字符是空格，则将P2指向的位置依次赋值为’0’(P2–), ‘2’(P2–), ‘%’(P2–)，然后P1–；若当前P1指向的字符不是空格，就将当前P1指向的字符复制到P2指向的位置。直至P1和P2指向同一位置（表明所有空格都已替换完毕）。
因为所有字符都只复制（移动）一次，因此算法时间复杂度为O(n)，空间复杂度为O(1)。
Java代码
import java.util.Scanner;
/**
* 剑指offer 面试题5 替换空格
* @author QingXi
*
*/
public class Solution5 {
/**
* 这种思路更直白：逐个扫描字符，若是空白字符，则将“ ”追加至结果字符串；
* 否则将当前字符追加至结果字符串。
* @param str
* @return 替换后的字符串
*/
public static String
replaceSpace(StringBuffer str) {
String result =
"";
if(str.equals(
"")) {
return result;
}
for (
int i =
0; i < str.length(); i++) {
if(str.charAt(i) ==
' ') {
result = result +
" ";
}
else {
result = result + str.charAt(i);
}
}
return result;
}
/**
* 从前往后扫描
* @param str
* @return 替换后的字符串
*/
public static String
replaceBlank(String str) {
if(str.equals(
"") || str.length() ==
0) {
return "";
}
int pos =
0;
String replace =
" ";
while(pos < str.length()) {
String curStr = str.substring(pos, pos +
1);
if (curStr.equals(
" ")) {
str = str.substring(
0, pos) + replace + str.substring(pos +
1);
pos = pos +
2;
}
else {
pos = pos +
1;
}
}
return str;
}
public static void main(String[] args) {
Scanner sc =
new Scanner(System.in);
while(sc.hasNextLine()) {
String str = sc.nextLine();
System.out.println(replaceBlank(str));
System.out.println(replaceSpace(
new StringBuffer(str)));
}
}
}
C代码
#include<stdio.h>
void replaceBlank(
char str[],
int length)
{
if(
str == NULL || length <=
0)
{
return;
}
int originalLength =
0;
int blankNumber =
0;
int i =
0;
while(
str[i] !=
'\0')
{
originalLength++;
if(
str[i] ==
' ')
{
blankNumber++;
}
i++;
}
int newLength = originalLength + blankNumber *
2;
if(newLength > length)
{
return;
}
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >=
0 && indexOfNew > indexOfOriginal)
{
if(
str[indexOfOriginal] ==
' ')
{
str[indexOfNew] =
'0';
indexOfNew--;
str[indexOfNew] =
'2';
indexOfNew--;
str[indexOfNew] =
'%';
indexOfNew--;
}
else
{
str[indexOfNew] =
str[indexOfOriginal];
indexOfNew--;
}
indexOfOriginal--;
}
}
int main()
{
char str[
1000];
while(gets(
str))
{
replaceBlank(
str,
1000);
puts(
str);
}
return 0;
}
