需求：
请实现一个函数，把字符串中的每个空格替换成"%20"，例如，输入"We are happy!"，则输出"We%20are%20happy!"。
分析：
思路一
直接从头开始替换。
1.从W开始遍历，找到第一空格 We后面的空格；
2.找到字符串结尾的地方，把We空格之后所有的字符串都往后移动两个位置(因为%20比空格多占两个位置)；
3.把We后面的空格替换成%20，继续查找下一个空格，即重复步骤1；
4.找到最后的结束符结束循环。
从头开始替换法，由于每次遇到空格都需要把空格后面的字符往后移动2个空格，时间复杂度为O(n**2)。
见示例代码replaceSpaceFromHead。
思路二
从尾部开始替换。
1.先从头开始把字符串遍历一次，统计其中的空格数量；
2.计算如果能够成功替换的话，字符的总长度是2*空格数+原始字符串长度。(因为%20比空格多占两个位置，所以多出来的长度应该是空格数的两倍)；
3.从最后一个字符开始，如果字符不是空格，则一次把字符从最终的长度开始移动；
4.遇到空格，就是空格从后面的位置往前填写02%(因为是从后往前填)，并且把剩余空格数减一；
5.当空格数为0或者替换到第一个字符则停止循环。
从尾开始替换法，由于只需要把原始字符串遍历2次，每次的时间复杂都都是O(n)，所以整体时间复杂度为O(n)，比从头开始替换法效率更高。
见示例代码replaceSpaceFromTail。
c++示例代码
1 #include
2
3 using namespacestd;4 const int g_length = 100;5
6 /************************************************************************/
7 /*@brief 从头开始替换字符串中的空格8 /* @param info 字符串9 /* @param length 字符数组的可用长度10 /* @return false表示替换失败，success表示替换成功11 /************************************************************************/
12 bool replaceSpaceFromHead(char* info, const intlength)13 {14 if (!info || length <= 0)15 {16 return false;17 }18
19 int bSuccess = true;20 int currentLen = 0;21 int i = 0;22 //从头开始查找，一直到最后一个字符
23 while (info[i] != '\0')24 {25 //如果是空格，开始替换
26 if (info[i] == ' ')27 {28 int j =i;29 //找到字符串的末尾
30 while (info[j] != '\0')31 {32 ++j;33 }34 //长度不够了,失败。新长度是索引加上增加的两个字符加上1
35 if (j + 2 + 1 >=length)36 {37 bSuccess = false;38 break;39 }40 //把每个字符往后活动两个位置
41 while (j >i)42 {43 info[j + 2] =info[j];44 --j;45 }46 //把当前的空格替换成%20然后继续查找下一个空格
47 info[i] = '%';48 info[i + 1] = '2';49 info[i + 2] = '0';50 i += 2;51 }52 //如果不是空格继续找下一个
53 else
54 {55 ++i;56 }57 }58 returnbSuccess;59 }60
61 /************************************************************************/
62 /*@brief 从尾开始替换字符串中的空格63 /* @param info 字符串64 /* @param length 字符数组的可用长度65 /* @return false表示替换失败，success表示替换成功66 /************************************************************************/
67 bool replaceSpaceFromTail(char* info, const intlength)68 {69 if (!info || length <= 0)70 {71 return false;72 }73
74 int bSuccess = true;75 int currentLen = 0;76 int i = 0;77 int spaceNum = 0;78 //查看有多少个空格
79 while (info[i] != '\0')80 {81 if (info[i] == ' ')82 {83 spaceNum += 1;84 }85 ++i;86 }87
88 //最终长度是索引加上增加的两个字乘空格数符加上1
89 int newLen = i + spaceNum * 2 + 1;90 //长度不够直接返回替换失败
91 if (newLen >length)92 {93 return false;94 }95
96 //当空格数为0就可以停止循环了
97 for (int j= newLen; spaceNum > 0 && i > 0; --i)98 {99 if (info[i] != ' ')100 {101 info[j] =info[i];102 --j;103 }104 else
105 {106 //把当前的空格替换成%20然后继续查找下一个空格
107 info[j] = '0';108 info[j - 1] = '2';109 info[j - 2] = '%';110 j -= 3;111 spaceNum -= 1;112 }113 }114
115 returnbSuccess;116 }117
118 intmain()119 {120 char szInfo[g_length] = { "We are happy!"};121 char szInfo1[g_length] = { "We are happy!"};122
123 cout << "原始字符串：" << endl << szInfo <
125 bool success =replaceSpaceFromHead(szInfo, g_length);126
127 cout << endl << "从头开始替换法：" <
133 {134 cout << "替换失败" <
137 success =replaceSpaceFromTail(szInfo1, g_length);138
139 cout << endl << "从尾开始替换法：" <
145 {146 cout << "替换失败" <
149 cout <
151 return 0;152 }
测试结果
