983
CareerCup之1.5 空格替換
【題目】
原文：
1.5 Write a method to replace all spaces in a string with ‘%20’.
譯文：
寫一個函數，把字符串中所有的空格替換為%20 。
【分析】
我們首先應該想到的是原來一個空格字符，替換之後變成'%','2','0'三個字符，因此字符串會變長。如果是在原來的字符串上做替換
，那麼我們就有可能覆蓋修改在該字符串後麵的內存。如果是創建信的字符串並在新的字符串上做替換，那麼我們自己可以分配足夠的
內存。由於兩種不同的解決方案，我們應該向麵試官問清楚，讓他們明確告訴我們需求。假設麵試官讓我們在原來的字符串上做替換，
並且保證輸入的字符串後麵有足夠多的空餘內存。
【思路一】
我們最應該想到的方法就是從頭掃描字符串，每一次遇到空格字符的時候就做替換。由於是把一個字符替換成三個字符，我們必須把
空格後麵的所有字符都想後麵移動兩個位置，否則就有兩個字符被覆蓋了。
舉個例子：
我們從頭掃描“ we are happy.”中的每一個空格替換成"%20"。
假設字符串的長度是n。對每一個空格字符，需要移動後麵O（n）個字符，因此含有O（n）個空格字符的字符串而言總的時間複雜度
為O（n^2）。
【思路二】
我們可以先遍曆一遍字符串，這樣我們先統計出空格字符的個數，並由此計算出替換空格字符之後的字符串的總長度。
每替換一個空格，長度增加2，因此替換以後的字符串長度等於原來字符串長度加上2*（空格數目）。
舉個例子：“ we are happy.”
這個字符串的長度為14，裏麵有兩個空格，因此替換之後的字符串長度為18.
我們從字符串的後麵開始複製和替換。首先準備兩個指針p1,p2。p1指向原始字符串的末尾，p2指向替換之後的字符串的末尾。
接下來我們向前移動指針p1，逐個把它指向的字符複製到p2指向的位置，直到碰到第一個空格字符為止。碰到第一個空格之後
把p1向前移動一個位置，在p2之前插入字符串“%20”。由於“%20”的長度為3，同時也要把p2向前移動三個位置。我們接著複製，直到
碰到第二個空格，進行同樣的操作。
【代碼一】
/*********************************
* 日期：2014-05-13
* 作者：SJF0115
* 題目: 替換空格
* 來源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
//替換空格
char* ReplaceBlank(char* str){
int i;
int len = strlen(str);
if(len <= 0){
return str;
}
//統計空格個數
int count = 0;
for(i = 0;i < len;i++){
if(str[i] == ' '){
count++;
}
}
//p1 指向原始字符串的末尾
int p1 = len;
//p2 指向替換之後的字符串的末尾
int p2 = len + 2*count;
//開辟一個字符串
char *str2 = new char[p2+1];
//替換
while(p1 >= 0){
if(str[p1] == ' '){
p1--;
str2[p2--] = '0';
str2[p2--] = '2';
str2[p2--] = '%';
}
else{
str2[p2--] = str[p1--];
}
}
return str2;
}
int main(){
char* str = "we are happy.";
str = ReplaceBlank(str);
cout<<str<<endl;
return 0;
}
最後更新：2017-04-03 12:56:41