在网络编程中，需要将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的位置添加' '。
代码：
void ReplaceBlank(char str[], int maxLength) { if(str == NULL || maxLength <=0) return; //calculate the new length after replacing and number of Blanks int originalLength = 0; int numberOfBlank = 0; int index = 0; for(index = 0; str[index] != ' '; index++) { if(str[index] == ' ') ++numberOfBlank; } originalLength = index+1; //if the number of blank is 0, nothing changes if(numberOfBlank==0) return; //if the new length exceeds the max length int newLength = originalLength+2*numberOfBlank; if (newLength > maxLength) { cout << "new Length exceeds the max Length!" << endl; return; } //start at the character before ' ' 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 ' ' at last str[newLength-1] = ' '; }
完整代码：
#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 Blanks int originalLength = 0; int numberOfBlank = 0; int index = 0; for(index = 0; str[index] != ' '; index++) { if(str[index] == ' ') ++numberOfBlank; } originalLength = index+1; //if the number of blank is 0, nothing changes if(numberOfBlank==0) return; //if the new length exceeds the max length int newLength = originalLength+2*numberOfBlank; if (newLength > maxLength) { cout << "new Length exceeds the max Length!" << endl; return; } //start at the character before ' ' 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 ' ' at last str[newLength-1] = ' '; } void test(char str[], int maxLength) { cout << "-----------test-------------" << endl; printf("Original: %s ", str); ReplaceBlank(str, maxLength); printf("Replaced: %s ", str); cout << "-----------end---------------" << endl; } int main() { /* char str[50] = "hello world and s"; ReplaceBlank(str, 50); printf("%s ", 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名企面试官精讲典型编程题》