題目描述
請實(shí)現(xiàn)一個函數(shù)卸夕，將一個字符串中的空格替換成“%20”怔匣。例如简烘，當(dāng)字符串為We Are Happy藏斩。則經(jīng)過替換之后的字符串為We%20Are%20Happy躏结。
通過判斷空格的個數(shù)來確定轉(zhuǎn)換后的字符串長度后，我們一般會想到由前往后替換空格狰域，但是如此之來，后面的字符需要多次移動黄橘，導(dǎo)致效率低下兆览。反過來，如果由后往前進(jìn)行替換塞关，那么需要改變位置的字符只需要移動一次抬探，時間復(fù)雜度為O(n)。
class Solution {
public:
void replaceSpace(char *str, int length) {
int blank = 0;
for (int i = 0; i < length; i++) {
if (str[i] == ' ')
blank++;
}
int newLength = length + blank * 2;
for (int i = length - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[--newLength] = '0';
str[--newLength] = '2';
str[--newLength] = '%';
} else {
str[--newLength] = str[i];
}
}
}
};
附上本地的IDE測試版：
#include <iostream>
using namespace std;
class Solution {
public:
void replaceSpace(char *str, int length) {
int blank = 0;
for (int i = 0; i < length; i++) {
if (str[i] == ' ')
blank++;
}
int newLength = length + blank * 2;
for (int i = length - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[--newLength] = '0';
str[--newLength] = '2';
str[--newLength] = '%';
} else {
str[--newLength] = str[i];
}
}
}
};
int main() {
// 前提是字符串的空間足夠大
// char str[1024] = "We Are Happy";
char *str = new char[1024];
cout << "請輸入字符串：" << endl;
cin.getline(str, 1024);
int length = 0, i = 0;
while (str[length] != '\0')
length++;
Solution s;
s.replaceSpace(str, length);
cout << "替換空格后的結(jié)果：" << endl;;
while (str[i] != '\0') {
cout << str[i];
i++;
}
return 0;
}
