题目：请实现一个函数，将一个字符串中的空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy。
不好解法：遍历，找空格，插“ ”,其中插入包括先移动，后赋值。这样的解法时间复杂度o（n^2）
优秀解法：遍历一遍字符串，统计空格，计算出插入后的总长度。然后从字符串的后面开始复制和替换，如此，时间复杂度o(n)
#include <stdio.h> #include <iostream> //param length 数组长度 bool ReplaceBlank(char string[], int length) { if (string == NULL || length <= 0) return false; int p = 0; //原字符串结尾 int q = 0; //填充后的结尾 int blankCount = 0; while (string[p] != '\0') { if (string[p] == ' ') blankCount++; ++p; } q = p + 2 * blankCount; if (q > length - 1) //越界 return false; while (p >= 0 && p < q) { if (string[p] == ' ') { string[q--] = '0'; string[q--] = '2'; string[q--] = '%'; --p; continue; } string[q--] = string[p--]; } return true; } int main() { char string[1024] = "we are happy!"; char string2[1024] = " haha ha "; printf("%s\n", string); if (ReplaceBlank(string, 1024)) printf("%s\n", string); else printf("error\n"); printf("%s\n", string2); if (ReplaceBlank(string2, 1024)) printf("%s\n", string2); else printf("error\n"); system("pause"); return 0; }
拓展题：有两个排序数组A1和A2，内存在A1的末尾有足够多的多余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中，并且所有数字有序。
解题思维与上题类似，如果遍历A2插入到A1中则会造成多次移动A1中的元素，时间复杂度o（n^2）。
如果先计算出插入后的长度，然后从A1和A2的末尾开始比较，谁大把谁插入新的末尾，以此类推一直到A1或A2遍历结束，所有元素移动一次，时间复杂度O(n)
#include <stdio.h> #include <iostream> using namespace std; //把一个有序数组插入到另一个有序数组中o（n）解法. b插到a中 void OredrArrayInsert(double *a, double *b, int len_a, int len_b) { int len = len_a + len_b; //插入后的长度 while (len > 0 && len_a > 0 && len_b > 0) { if (a[len_a - 1] > b[len_b - 1]) { a[len - 1] = a[len_a - 1]; --len_a; --len; } else { a[len - 1] = b[len_b - 1]; --len_b; --len; } } //a拷贝完全，b还没有拷贝完 while (len > 0 && len_b > 0) { a[len - 1] = b[len_b - 1]; --len; --len_b; } //b拷贝完全，a还没有拷贝完 while (len > 0 && len_a > 0) { a[len - 1] = a[len_a - 1]; --len; --len_a; } } void printArray(double *a, int len) { for (int i = 0; i < len; i++) cout << a[i] << ","; cout << endl; } int main() { double R[] = {12,34,20,15,9,25,27,13}; cout << sizeof(R) / sizeof(double) << endl; QuickSort(R, 0, 7); for (int k = 0; k < 8; k++) cout << R[k] << " "; cout << endl; double a[1024]; for (int i = 0; i < 10; i++) a[i] = i; double b[] = {2,3,4,9,15,22,30,70}; printArray(a,10); printArray(b,8); //printArray(a, 17); OredrArrayInsert(a, b, 10, 8); printArray(a, 18); system("pause"); return 0; } 举一反三：合并两个数组（包括字符串）时，如果从前往后复制每个数字或者字符需要重复移动，那么可以考虑从后往前复制，这样就可以减少移动次数，从而提高效率。
