《剑指Offer》第2章笔记 字符串

字符串的使用频率非常高，为了优化，很多语言都对字符串做了特殊的规定。

C/C++中每个字符串都以字符 \0 做为结尾，这样便于运行时判断字符数组的尾部，由于这个特点，字符串数组的长度比真实字符串长度要多1才可以，这样容易导致一些错误：

char str[10];
strcpy(str, "0123456789"); // Error

为了节省内存，C/C++把常量字符串放到一个单独的内存区域，当几个指针赋值给相同的常量字符串时，实际上会指向相同的内存地址。但用常量内存来初始化字符数组时，情况又有所不同了，看下面的例子：

int main() {
    char str1[] = "hello world";
    char str2[] = "hello world";

    char* str3 = "hello world";
    char* str4 = "hello world";

    printf("str1 =%p\n", str1); // 0061fe04
    printf("str2 =%p\n", str2); // 0061fdf8
    printf("str3 =%p\n", str3); // 00409001
    printf("str4 =%p\n", str4); // 00409001
    return 0;
}

str1和str2是两个字符数组，在初始化赋值时，运行时为为他们分配两个长度为12字节的内存空间，并把字符串赋值到数组中去（而不是直接拷贝字符串常量地址），所以他们的初始地址是不同的。

str3和str4是两个指针，不需要再分配内存来存储内容，只需要传递地址，所以他们就拷贝了同一个地址。

面试题5：替换空格

实现一个函数，把字符串的每个空格替换成%20，例如输入We are happy.，则输出We%20are%20happy.。

题目来自于网络编程中的URL特殊字符编码，有时候服务器不一定支持一些特殊字符URL，所以需要先将特殊转换成ASCII码的两位十六进制表示，比如空格的ASCII码是32，即十六进制的0x20，空格被替换成%20，比如#的ASCII码为35，十六进制0x23，在URL中被替换成%23。

一般有两种解决方向：

• 在原字符数组上进行处理；
• 申请新字符数组，将新内容写进去；

在面试过程中遇到这样的问题，如果确定题目中没有限定说明，可以向面试官进一步地问清楚应该考虑什么样的限定条件。

在这里我们假设（作者假设）面试官需要在原字符数组上替换，输入的字符串后面有足够多的内存空间。

我们仍然从最简思路入手：

• 思路1：在字符串中进行遍历，当碰到空格时，将空格替换为%20，由于替换的字符串比空格多2个字符，为了放入%20，所以要将后续的字符串后移两位，重复该操作直到字符串没有空格。

假设字符串长度n，对于每个空格字符，需要移动后面O(n)个字符，所以时间开销是O(n^2)。

显然这个方法过于简单，还不是最优解，观察可以发现，有些字符串被反复后移，但其实对于一个固定空格个数的字符串，这些字符串所应该处的最终位置我们是可以计算出来的，比如We are happy.中We前面没有空格，不需要向后移动，are前面有1个空格，所以字符串会被后移2位，happy.前面有2个空格，需要移动4位。

所以对于某些字符串其最终的位置反而是通过计算得到的，不需要反复的重复移动（拷贝字符串时间开销大）。

• 思路2：使用一个空格计数器，在移动字符串时，根据当前空格计数器来判断当前字符需要后移多少位，然后直接将字符移动到目标位置上，遇到空格时，根据计算的后移位置，直接顺序写入%20。时间开销因为只需要遍历一次字符串，所以是O(n)。

这样的思路还是有亿点点问题需要考虑，如果从头开始移动字符串，则后面的字符串还没有空出来时，就需要先移动后面的字符串，这样就导致问题变得稍微有点复杂，所以我们可以反过来，从尾部开始处理移动操作。

• 思路3：先遍历一次字符串，统计空格出现次数，计算最终字符串的长度，然后从尾部开始处理移动，申请两个指针，一个指向原字符位置，一个指向移动目标位置，当遇到普通字符时，直接转移，遇到空格时，在目标位置写入替换字符串。时间开销仍然是O(n)。

完整实现代码:

#include <iostream>
#include <cstring>

bool replace(char* str, char* ori, char* rep) {
    if(str != nullptr && ori != nullptr && rep != nullptr
       && strlen(str) > 0 && strlen(ori) > 0 && strlen(rep) > 0) {
        int count = 0;
        int ori_len = strlen(ori);
        int rep_len = strlen(rep);
        for(int i = 0; i < strlen(str); i++) {
            if(strncmp((str+i), ori, ori_len) == 0) {
                count++;
            }
        }
        if(count == 0) {
            return true;
        }
        char* po = str + strlen(str) + 1;
        char* pr = po + count * (rep_len - ori_len);
        while(po >= str) {
            if(strncmp(po, ori, ori_len) == 0) {
                for(char* tmp = rep + (rep_len - 1); tmp >= rep; tmp--) {
                    *pr = *tmp;
                    pr--;
                }
                po--;
            } else {
                *pr = *po;
                po--;
                pr--;
            }
        }
        return true;
    } else {
        return false;
    }
}

int main() {
    char str[100] = "We are happy.";
    char ori[10] = " ";
    char rep[10] = "%20";
    if(replace(str, ori, rep)) {
        printf("%s\n", str);
    } else {
        printf("Error\n");
    }
}

Tips：代码和原作者的实现有出入，实现了相对来说比较通用的字符串替换，但是方法以及代码仅仅只针对这道题目而言是有效的，还有非常多该题目以外的问题其实是没有考虑到的，例如需要被替换不是单个的空格而是多个空格甚至是任意字符、替换的字符串如果长度小于被替换字符串该怎么处理，等等（修改上述代码中的初始字符串即可看到结果会出现问题）；不过不在这里继续讨论，可以自行尝试思考。

拓展题练习题： 已排序的两个数组A1和A2，A1尾部有足够多的空间容纳A2，将A2的所有数组插入A1中，并且最终A1中所有数字是有序的。