在网络编程中，需要将URL参数中含有的特殊字符通过在'%'后加上ASCII码的两位十六进制的方法，转换成服务器端能够识别的字符，如空格的ASCII码为32即16进制的0x20，则需要替换为"%20"。
题目：请实现一个函数，把传入char*字符串中的每个空格替换成"%20"，例如输入"We are happy."，则输出"We%20are%20happy."
时间复杂度为O(n)的解法思路：
首先遍历字符串，得到字符串长度originalLength并统计空格数numberOfBlank，可计算出替换后的字符串长度newLength = originalLength+2*numberOfBlank；
从字符串的尾部开始复制并向前移动，用两个下标IndexOfOriginal和IndexOfNew分别标记目前所指的原字符位置和替换后的字符位置；
当IndexOfOriginal指向空格时，IndexOfNew下标所指的字符及其往前1、2个位置分别替换为'0'、'2'、'%'，替换完成后IndexOfOriginal向前移动一格，IndexOfNew相应向前移动3格，否则都往前移动一格；
最后在字符串尾部即下标为newLength-1的位置添加'\0'。
代码：
void ReplaceBlank(char str[], int maxLength) {if(str == NULL || maxLength <=0)return;//calculate the new length after replacing and number of Blanksint originalLength = 0;int numberOfBlank = 0;int index = 0;for(index = 0; str[index] != '\0'; index++) {if(str[index] == ' ')++numberOfBlank;}originalLength = index+1;//if the number of blank is 0, nothing changesif(numberOfBlank==0)return;//if the new length exceeds the max lengthint newLength = originalLength+2*numberOfBlank;if (newLength > maxLength) {cout << "new Length exceeds the max Length!" << endl;return;}//start at the character before '\0'int indexOfOriginal = originalLength-2;int indexOfNew = newLength-2;while (indexOfOriginal>=0 && indexOfNew > indexOfOriginal) {if (str[indexOfOriginal] == ' ') {str[indexOfNew--] = '0';str[indexOfNew--] = '2';str[indexOfNew--] = '%';} else {str[indexOfNew--] = str[indexOfOriginal];}--indexOfOriginal;}//add a '\0' at laststr[newLength-1] = '\0';}
完整代码：
#include <iostream>#include <stdio.h>using namespace std;void ReplaceBlank(char str[], int maxLength) {if(str == NULL || maxLength <=0)return;//calculate the new length after replacing and number of Blanksint originalLength = 0;int numberOfBlank = 0;int index = 0;for(index = 0; str[index] != '\0'; index++) {if(str[index] == ' ')++numberOfBlank;}originalLength = index+1;//if the number of blank is 0, nothing changesif(numberOfBlank==0)return;//if the new length exceeds the max lengthint newLength = originalLength+2*numberOfBlank;if (newLength > maxLength) {cout << "new Length exceeds the max Length!" << endl;return;}//start at the character before '\0'int indexOfOriginal = originalLength-2;int indexOfNew = newLength-2;while (indexOfOriginal>=0 && indexOfNew > indexOfOriginal) {if (str[indexOfOriginal] == ' ') {str[indexOfNew--] = '0';str[indexOfNew--] = '2';str[indexOfNew--] = '%';} else {str[indexOfNew--] = str[indexOfOriginal];}--indexOfOriginal;}//add a '\0' at laststr[newLength-1] = '\0';}void test(char str[], int maxLength) {cout << "-----------test-------------" << endl;printf("Original: %s\n", str);ReplaceBlank(str, maxLength);printf("Replaced: %s\n", str);cout << "-----------end---------------" << endl;}int main() {/*char str[50] = "hello world and s";ReplaceBlank(str, 50);printf("%s\n", str);*/char str1[50]="hello world and s";char str2[50]="";char str3[20]="hello world! fdsjkd";char str4[50]=" helloweroddfsd";char str5[50]=" ";test(str1, 50);test(str2, 50);test (NULL, 50);test(str3, 20);test(str4, 50);test(str5, 50);return 0;}
参考资料：《剑指Offer名企面试官精讲典型编程题》
