題目描述:請實現(xiàn)一個函數(shù)芥玉，把字符串中的每個空格替換成"%20"纲酗。
樣例輸入:"We are happy."
樣例輸出："We%20are%20happy."
說明：假設輸入的字符串有足夠的內(nèi)存空間吏够，可以裝下替換后的新字符串推正，請在原串的基礎上進行替換。
解題思路:
這一題很容易想到從頭到尾遍歷缸濒，然后替換空格足丢。但由于一個空格替換成三個字符，我們必須把空格之后的字符向后移動兩位庇配。這樣一來時間復雜度即為O(n^2).不是很好的解法斩跌。合理的做法是，先遍歷一遍字符串捞慌，統(tǒng)計出空格的數(shù)量耀鸦，然后算出把空格替換成‘%20’之后的新的字符串的長度。使用兩個指針啸澡，一個指向原來字符串的末尾袖订，另一個指向替換之后的字符串的末尾。遇到普通字符就把字符放到新的串上嗅虏，兩個指針分別向前走一步洛姑，遇到空格原字符串的指針向前走一步新的向前走三步，并替換成'%20'.如此一來便可在O(n)的時間復雜度之內(nèi)完成皮服。
話不多說楞艾，代碼如下(C++):
//
// main.cpp
// replaceBlankSpace
//
// Created by 孫艷東 on 2017/11/30.
// Copyright ? 2017年 孫艷東. All rights reserved.
//
/*
*題目描述:請實現(xiàn)一個函數(shù)参咙，把字符串中的每個空格替換成‘%20’。例如輸入'We are happy.'
*則輸出'We%20are%20happy.'硫眯，假設原來輸入字符串之后有足夠多的內(nèi)存蕴侧。在原來的字符串上進行替換
*
*解題思路：先統(tǒng)計出有多少個空格，計算出替換后的長度两入，然后創(chuàng)建一個新的數(shù)組净宵，用兩個指針從后往前插入。
*時間復雜度為O(n)
*/
#include <iostream>
using namespace std;
void replaceBank(char str[],int length) {
if (str == NULL || length < 0) {
return;
}
int originStrLength = 0;
int newStrLength = 0;
// 計算替換后的長度
int i = 0;
while (str[i] != '\0') { // 不是輸入結束
originStrLength ++;
if (str[i] == ' ') {
newStrLength ++;
}
i ++;
}
newStrLength = originStrLength + newStrLength * 2; // 替換后的實際長度
int indexOfOrigin = originStrLength;
int indexOfNew = newStrLength;
while (indexOfOrigin >= 0 && indexOfNew > indexOfOrigin) {
if (str[indexOfOrigin] == ' ') {
str[indexOfNew --] = '0';
str[indexOfNew --] = '2';
str[indexOfNew --] = '%';
}else {
str[indexOfNew --] = str[indexOfOrigin];
}
indexOfOrigin --;
}
}
int main(int argc, const char * argv[]) {
char str[1024];
cin.get(str, 1024);
replaceBank(str, 1024);
std::cout << str;
return 0;
}
