• C/C++ 中每个字符串都以字符’\0’作为结尾
    • /C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，它们实际上会指向相同的内存地址。

    题目：请实现一个函数，把字符串中的每个空格替换成”%20”。例如输入“We arehappy.”，则输出“We%20are%20happy.”。

    • 在网络编程中，如果URL参数中含有特殊字符，如空格、’#’等，可能导致服务器端无法获得正确的参数值。
    • 我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在’%’后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成”%20”。再比如’#’的ASCII码为35，即十六进制的0x23，它在URL中被替换为”%23”。
    • 时间复杂度为O（n2）的解法，不足以拿到Offer

    image.png
    随着空格数量的增多，后面字符需要移动的次数就越多

    • 时间复杂度为O（n）的解法，搞定Offer就靠它了
      1. 先遍历一次字符串，这样就能统计出字符串中空格的总数，并可以由此计算出替换之后的字符串的总长度
      2. 每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上 2 乘以空格数目

    image.png

    • 准备两个指针，P1和 P2。P1 指向原始字符串的末尾，而 P2 指向替换之后的字符串的末尾
    • 向前移动指针P1，逐个把它指向的字符复制到 P2指向的位置，直到碰到第一个空格为止
    • 碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串”%20”。由于”%20”的长度为3，同时也要把P2向前移动3格
    1. /* length为字符数组string的总容量 */
    2. void ReplaceBlank(char string[], int length)
    3. {
    4.     if((string == NULL) && (length <= 0)){
    5.         return;        //直接退出
    6.     }
    8.     /* originalLength为字符串string的实际长度
    9.      * numberOfBlank为字符串中空格数
    10.      */
    11.     int originalLength = 0;
    12.     int numberOfBlank = 0;
    13.     int i = 0;
    14.     while(string[i] != '\0'){
    15.         ++originalLength;
    16.         if(string[i] == ' '){
    17.             ++numberOfBlank;
    18.         }
    19.         ++i;
    20.     }
    22.     /* newLength为把空格替换成%20后的长度 */
    23.     int newLength = originalLength + 2*numberOfBlank;
    24.     if(newLength > length){
    25.         return;    /* 所需空间大于实际的，无法处理 */
    26.     }
    28.     int indexOfOriginal = originalLength;            // 指针P1
    29.     int indexOfNew = newLength;                        // 指针P2
    30.     while((indexOfOriginal >= 0) && (indexOfNew > indexOfOriginal))
    31.     {
    32.         if(string[indexOfOriginal] == ' '){
    33.             string[indexOfNew--] = '0';
    34.             string[indexOfNew--] = '2';
    35.             string[indexOfNew--] = '%';
    36.         }eles{
    37.             string[indexOfNew--] = string[indexOfOriginal];
    38.         }
    39.         --indexOfOriginal;
    40.     }
    41. }

    有两个排序的数组A1和A2，内存在A1 的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的。

    • 很多人首先想到的办法是在A1中从头到尾复制数字，但这样就会出现多次复制一个数字的情况。更好的办法是从尾到头比较A1和A2中的数字，并把较大的数字复制到A1的合适位置。

    • 合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。

      1. /* A1Size    A1数组内容实际大小
      2. * A2Size    A2数组内容实际大小
      3. * Length    A1实际空间大小
      4. * 将后一个数组的数字合并到第一个数组内，并保持排序
      5. */
      6. void MergeSortArray(int A1[], int A1Size, int Length, int A2[], int A2Size)
      7. {
      8.   if((A1Size + A2Size) > Length)
      9.       return;
      11.   int indexOfA1 = A1Size-1;
      12.   int indexOfA2 = A2Size-1;
      13.   int indexOfNew = indexOfA1 + indexOfA2;
      15.   /* A1遍历完，A2未遍历完时，不能退出循环
      16.    * A2遍历完，A1未遍历完时，直接退出循环
      17.    */
      18.   while((indexOfNew >= indexOfA1) && (indexOfA2 >= 0))
      19.   {
      20.       if((indexOfA1 >= 0) && (A1[indexOfA1] > A2[indexOfA2])){
      21.           A1[indexOfNew] = A1[indexOfA1--];
      22.       }else{
      23.           A1[indexOfNew] = A2[indexOfA2--];
      24.       }
      25.       --indexOfNew;
      26.   }
      27. }