跳转至

3.2 字符串

字符串是否若干字符组成的序列。 由于字符串在编程时使用的频率非常高,为了优化,很多语言都对字符串做了特殊的规定.

C/C++中每个字符串都以字符'\0'作为结尾,这样我们就能很方便地找到字符串最后尾部.

但由于这个特点, 每个字符串中都有一个额外的字符开销,稍不留神就会造成字符串的越界.

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

我们先声明一个长度为10的字符数组,然后把字符串"0123456789"复制到数组中. "0123456789"看起来只有10个字符, 但实际上它的末尾还有一个'\0'字符,因此它的实际长度为11字节. 要正确的复制该字符串,至少需要一个长度为11字节的数组.

为了节省内存, C/C++把常量字符串放到单独的一个内存区域.当几个指针赋值给相同的常量字符串时,他们实际上会指向相同的内存地址. 但用常量内存初始化数组,情况却有所不同,下面通过一个面试题来学习这一知识点. 运行下面的代码, 得到的结果是什么?

#include <iostream>
using namespace std;


int main(int argv, const char* argc)
{
    char str1[] = "hello world";
    char str2[] = "hello world";

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

    if (str1 == str2)
        cout << "str1 and str2 are same" << endl;
    else
        cout << "str1 and str2 are not same" << endl;

    if (str3 == str4)
        cout << "str3 and str4 are same" << endl;
    else
        cout << "str3 and str4 are not same" << endl;

    return 0;
}

str1 和 str2 是两个字符串数组,我们会为他们分配两个长度为12字节的空间, 并把"hello world"的内容分别赋值到数组中去. 这是两个初始地址不同的数组, 因此str1 和 str2的值也不相同.

str3 和 str4 是两个指针,我们无须为他们分配内存以存储字符串的内容,而只需要把他们指向"hello world"在内存中的地址就可以了,由于"hello world"是常量字符串,他在内存中只有一个拷贝,因此str3 和 str4 指向同一个地址.

面试题5: 替换空格

Question

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

Tip

在网络编程中,如果url参数含有特殊字符,如空格,"#"等, 则可能导致服务器端无法获取正确的参数,我们需要将这些特殊字符转换成服务器可以识别的字符.转换的规则是在'%'的后面跟上ASCII码的两位十六进制表示. 比如空格的ASCII码是32, 即十六进制的0x20, 因此空格被替换成%20, 再比如'#'的ASCII码为35,即表示为0x23, 他在url中被替换为%23.

看到这个题目, 我们首先应该想到的是原来一个空格字符, 替换之后变成'%', '2'和'0' 这3个字符,因此字符串会变长, 如果是在原来的字符串上进行替换, 就有可能覆盖修改再该字符串后面的内存. 如果是创建新的字符串并在新的字符串上进行替换,那么我们可以自己分配足够多的内存. 由于有两种不同的解决方案,我们应该向面试官问清楚,让他明确告诉我们他的需求,假设面试官让我们在原来的字符串长进行替换,并且保证输入的字符串后面有足够多的空余内存.

解法一: 时间复杂度为O(n^2), 不足以拿到offer 遍历原字符数组, 遇到空格, 在把空格所在位置后面的元素往后移两个位置。 需要保证数组足够长。你会发现空格后面的字符可能存在被移动多次的可能。 解法二对这个问题就行了优化。

解法二: 时间复杂度为O(n),搞定offer就靠他了 先遍历一次字符串,统计空格的个数,并可以由此计算出替换之后字符串的总长度,我们从字符串的后面开始复制和替换,这样就避免了后面的字符可能移动多次的情况。

Answer

解法一: string_blank_replace1.cpp

解法二: string_blank_replace2.cpp

本题考点:

  • 考查应聘者对字符串的编程能力。
  • 考查应聘者分析时间效率的能力。
  • 考查应聘者对内存覆盖是否有高度的警惕。 在分析得知字符串会变长之后,我们能够意识到潜在问题,并主动和面试官沟通以寻找问题的解决方案。
  • 考查应聘者的思维能力。 在从前到后替换的思路和面试官否定之后,我们能迅速想到从后到前替换的方法。 这是解决此题的关键。

相关题目:

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

举一反三:

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