《剑指Offer》第二章笔记(下)

Posted on 2023-05-24 Edited on 2022-02-18 In Reading , Books , Computer Science

第二章面试需要的基础知识 (下)

2.3 数据结构

技术面试的重点。几种常见的数据结构包括:

数组和字符串。用连续内存分别存储数字和字符。
链表和树。操作涉及大量的指针，留意代码的鲁棒性。
栈和队列。分别与递归和广度优先遍历算法紧密相关。

2.3.1 数组

占据一块==连续的内存==并按照==顺序存储==数据。创建数组时，需要==首先指定数组的容量大小==，然后根据大小==预先分配内存==。

数组的==空间效率不是很好==，常有空闲的区域没有得到充分利用。数组的==时间效率很好==，由于数组中的内存是连续的，可以根据下标在\(O(1)\) 时间读/写元素。

可以根据数组时间效率高的优点来==实现简单的哈希表==：下标设为哈希表的键值 (Key) ，值设为哈希表的值 (Value) ，组成键值－值的配对。有了这样的哈希表，可以在\(O(1)\) 实现查找，从而可以快速高效地解决很多问题。

为了解决数组空间效率不高的问题，设计实现了多种==动态数组==，比如C++的STL中的vector。为数组开辟较小的空间，当目前容量不够用时再重新分配一块更大的空间 (vector: 每次扩充容量时，新的容量都是前一次的两倍)，把之前的数据复制到新的数组中，再把之前的内存释放，减少内存的浪费。但==扩充数组是消耗很大的操作==，对时间性能有负面影响，因此使用动态数组时要尽量减少改变数组容量大小的次数。

在C/C++中，当声明一个数组时，数组的名字也是一个指针，指向数组的第一个元素。可以用一个指针来访问数组。

但C/C++没有记录数组的大小，因此用指针访问数组中的元素时要确保不会越界。

例子: 运行下面的代码，请问输出是什么？

data1是一个数组，sizeof(data1)是求数组大小，因此是20字节。 data2声明为指针，sizeof(data2)在32位系统上是4字节。 C/C++中，当数组作为函数的参数进行传递时会自动退化为同类型的指针。因此尽管函数GetSize的参数data被声明为数组，但它会退化为指针，size3的结果仍然是4。

面试题3：二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如下面的二维数组就是每行、每列都递增排序。

如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。

在分析这个问题的时，很多人都会从数组中选取一个数字 (深色)，分3种情况来分析查找的过程。

当数组中选取的数字刚好和要查找的数字相等时，就结束查找过程。如果选取的数字小于要查找的数字，则目标应该在当前选取的位置的右边或者下边 (图2.1 (a)) 。如果选取的数字大于要查找的数字，则目标应该在当前选取的位置的上边或者左边 (图2.1 (b)) 。在上面的分析中，由于目标可能在两个区域中出现，而且这两个区域还有重叠，会比较复杂。分析复杂问题时，一个很有效的办法是从一个简单具体的例子来寻找普遍的规律。

以查找数字7为例来一步步分析查找的过程。之前我们在二维数组的中间选取目标，于是下一次要查找的是两个相互重叠的区域。如果我们从数组的一个角上选取目标，情况会不会变简单呢？过程如下图。

总结上述查找的过程，我们发现如下规律：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

下面是上述思路对应的参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool Find(int *matrix, int rows, int columns, int number)
{
    bool found = false;
    
    if (matrix != NULL && rows>0 && columns>0)
    {
        int row = 0;
        int column = columns - 1;
        while(row<rows && column >= 0)
        {
            if(matrix[row * columns + column] )
        }
    }
}

同理，我们也可以选取左下角的数字。但我们不能选择左上角或者右下角的数字。以左上角为例，如果当前的数字小于目标，则目标应该位于当前数字的右边或者下边，此时无法缩小查找范围。

测试用例：

包含查找的数字（是数组中的最大值和最小值; 介于数组中的最大值和最小值之间）。

没有查找的数字（大于数组中的最大值，小于数组中的最小值，在数组的最大值和最小值之间但数组中没有这个数字）。

特殊输入测试（输入空指针）。

本题考点：

考查应聘者对二维数组的理解及编程能力。可以根据行号和列号计算出相对于数组首地址的偏移量，从而找到对应的元素。

考查应聘者分析问题的能力。发现问题比较复杂时，能不能通过具体的例子找出其中的规律。

2.3.2　字符串

字符串是由若干字符组成的序列。字符串的==使用频率非常高==。为了优化，很多语言都对字符串做了==特殊的规定==。

C/C++中每个字符串都以字符'\0'作为结尾，这样就能很方便地找到尾部。但由于这个特点，每个字符串中都有一个额外字符的开销。

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

例题: 运行下面的代码，得到的结果是什么？

第一行: ”str1 and str2 are not same”。 str1和str2是两个初始地址不同的字符串数组，会为它们分配两个长度为12个字节的空间，并把"hello world"的内容分别复制到数组中去。

第二行: "str3 and str4 are same"。 str3和str4是两个指针，因此不会被分配内存以存储字符串的内容，而只需要把它们指向"hello world”在内存中的地址就可以了。由于"hello world”是常量字符串，它在内存中只有一个拷贝，因此str3和str4指向的是同一个地址。

在C#中，封装字符串的类型System.String中的内容是不能改变的。一旦试图改变String的内容，就会产生一个新的实例。例如:

在上述代码中，对str做了ToUpper和Insert两个操作，但结果都是生成一个新的String实例并返回，str本身的内容不会发生改变。用String作连续多次修改，每一次修改都会产生一个临时对象，这样开销太大会影响效率。为此C#定义了一个新的与字符串相关的类型StringBuilder，它能容纳修改后的结果。

类似，如果我们试图把一个常量字符串赋值给一个String实例，也不是把String的内容改成赋值的字符串，而是生成一个新的String实例。例如:

在上面的代码中，先判断String是值类型还是引用类型。类型String的定义是public sealed class String {...}。既然是class，那么String自然就是引用类型。接下来在方法ModifyString里，对text赋值一个新的字符串。但text的内容是不能被修改的。此时会先生成一个新的内容是"world"的String实例，然后把text指向这个新的实例。由于参数text没有加ref或者out，出了方法ModifyString之后，text还是指向原来的字符串，因此输出仍然是"hello"。

面试题4：替换空格

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

在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。

如果是在原来的字符串上做替换，那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换，那么我们可以自己分配足够多的内存。我们应该向面试官问清楚，让他明确告诉我们他的需求。

假设面试官让我们在原来的字符串上做替换，并且保证输入的字符串后面有足够多的空余内存。

时间复杂度为\(O (n^2)\)的解法: 最直观的做法是从头到尾扫描字符串，每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移两个字节，如图所示。

假设字符串的长度是\(n\)。对每个空格字符，需要移动后面\(O(n)\)个字符，因此对含有\(O(n)\)个空格字符的字符串而言总的时间效率是\(O(n^2)\)。

数组中很多字符都移动了很多次，能不能减少移动次数呢？可以换一种思路，把从前向后替换改成从后向前替换。

时间复杂度为\(O(n)\)的解法: 可以先遍历一次字符串，统计出字符串中空格的总数，并由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。

我们从字符串的后面开始复制和替换。首先准备两个指针，P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾。接下来向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。此时把P1向前移动1格，在P2之前插入字符串"%20"并将P2向前移动3格，如此类推。

面试时，==可以用示意图解释自己的思路==，使我们和面试官的交流变得更加高效。在面试官肯定我们的思路之后，就可以开始写代码了:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// length为数组string的总容量
void ReplaceBlank(char string[], int length)
{
    if (string == NULL && length <= 0)
        return;
    
    // originalLength为string的实际长度
    int originalLength = 0;
    int numberOfBlank = 0;
    for(int i=0; string[i] != '\0'; i++)
    {
        originalLength++;
        
        if (string[i] == ' ')
            numberOfBlank++;
    }
    
    // newLength为将空格替换为'%20'之后的长度
    int newLength = originalLength + numberOfBlank * 2;
    if (newLength > length)
        return;
    
    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >=0 && indexOfNew > indexOfOriginal)
    {
        if (string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }
        
        -- indexOfOriginal;
    }
}

测试用例：

输入的字符串中包含空格（位于字符串的最前面，最后面，中间，连续多个空格）。

输入的字符串中没有空格。

特殊输入测试（字符串是个NULL指针、空字符串、只有一个空格字符、只有连续多个空格）。

本题考点：

考查对字符串的编程能力。

考查分析时间效率的能力。

考查对内存覆盖是否有高度的警惕。能够意识到潜在的问题，并主动和面试官沟通以寻找问题的解决方案。

考查思维能力。在从前到后替换的思路被面试官否定之后，能迅速想到从后往前替换的方法。

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

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

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

2.3.3　链表

由指针把若干个结点连接成链状结构。

我们说链表是一种==动态数据结构==，是因为在创建链表时，==无须知道链表的长度==。当插入一个结点时为新结点分配内存，然后调整指针的指向来确保新结点被链接到链表当中。由于没有闲置的内存，链表的==空间效率比数组高==。

如果单向链表的结点定义如下：

struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
}

则在链表末尾添加一个节点的C++代码如下:

void AddToTail(ListNode** pHead, int value)
{
    ListNode* pNew = new ListNode();
    pNew->m_nValue = value;
    pNew->m_nNext = NULL;
    
    if (*pHead == NULL)
    {
        *pHead = pNew;
    }
    else
    {
        ListNode *pNode = *pHead;
        
        while(pNode->m_pNext != NULL)
            pNode = pNode->m_pNext;
        
        pNode->m_pNext = pNew;
    }
}

如果想在链表中找到它的第i个结点，我们只能从头结点开始遍历链表，时间效率为\(O(N)\)。而在数组中，可以根据下标在\(O(1)\)内找到第i个元素。

在链表中找到第一个含有某值的结点并删除该结点的代码:

void RemoveNode(ListNode** pHead, int value)
{
    if (pHead == NULL || *pHead == NULL)
        return;
    
    ListNode* pToBeDeleted = NULL;
    if((*pHead)->m_nValue==value)
    {
        pToBeDeleted = *pHead;
        *pHead = (*pHead)->m_pNext;
    }
    else
    {
        ListNode* pNode = *pHead;
        while(pNode->m_pNext != NULL
           && pNode->m_pNext->m_nValue != value)
           pNode = pNode->m_pNext;
        
        if (pNode->m_pNext != NULL && pNode->m_pNext->m_nValue == value)
        {
            pToBeDeleted = pNode->m_pNext;
            pNode->m_pNext = pNode->m_pNext->m_pNext;
        }
    }
    
    if(pToBeDeleted != NULL)
    {
            delete pToBeDeleted;
            pToBeDeleted = NULL;
    }
}

除了简单的单向链表面试题: 面试题5“从尾到头输出链表”、面试题13“在\(O(1)\)时间删除链表结点”、面试题15“链表中的倒数第k个结点”、面试题16“反转链表”、面试题17“合并两个排序的链表”、面试题37“两个链表的第一个公共结点”等；

链表的其他形式面试题: 面试题45“圆圈中最后剩下的数字”(环形链表); 面试题27“二叉搜索树与双向链表” (双向链表); 面试题26“复杂链表的复制” (复杂链表: 链表中的结点中除了有指向下一个结点的指针，还有指向任意结点的指针。)

面试题5：从尾到头打印链表

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表结点定义如下：

struct ListNode
{
    int m_nValue;
    ListNode* m_pNext;
}

看到这道题后，很多人自然地想到把链表中链接结点的指针反转过来，就可以从头到尾输出了。但该方法会改变原来链表的结构。是否允许在打印链表的时候修改链表的结构？这个取决于面试官的需求，在面试的时候我们要询问清楚。

面试小提示： ==在面试中如果我们打算修改输入的数据，最好先问面试官是不是允许做修改==。通常打印是一个只读操作，我们不希望打印时修改内容。

假设面试官也要求这个题目不能改变链表的结构。

接下来我们想到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。这就是典型的“后进先出”，可以用栈实现这种顺序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void PrintListReversingly_Iteratively(ListNode* pHead)
{
    std::stack<ListNode*> nodes;
    
    ListNode* pNode = pHead;
    while(pNode != NULL)
    {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    
    while(!nodes.empty())
    {
        pNode = nodes.top();
        printf("%d\t", pNode->m_nValue);
        nodes.pop();
    }
}

由于用栈来实现这个函数，而递归本质上就是一个栈结构，因此可以很自然地用递归实现。每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身:
1
2
3
4
5
6
7
8
9
10
11
12
void PrintListReversingly_Recursively(ListNode* pHead)
{
    if(pHead != NULL)
    {
        if(pHead->m_pNext != NULL)
        {
            PrintListReversingly_Recursively(pHead->m_pNext);
        }
        
        printf("%d\t", pHead->m_nValue);
    }
}
递归代码看起来很简洁，但当链表很长时，函数调用的层级很深，可能导致函数调用栈溢出。显式用栈基于循环实现的代码的鲁棒性会好一些。

测试用例：

功能测试（输入的链表有多个结点; 只有一个结点）。

特殊输入测试（输入的链表头结点指针为NULL）。

本题考点：

考查对单项链表的理解和编程能力。

考查对循环、递归和栈3个相互关联的概念的理解。

2.3.4　树

除了根结点之外每个结点只有一个父结点，根结点没有父结点；除了叶结点之外所有结点都有一个或多个子结点，叶结点没有子结点。父结点和子结点之间用指针链接。

由于树的操作会==涉及大量的复杂指针操作==。

二叉树是树的一种特殊结构，在二叉树中每个结点最多只能有两个子结点。在二叉树中最重要的操作莫过于==遍历==。

前序遍历：先访问根结点，再访问左子结点，最后访问右子结点。图2.5中的二叉树的前序遍历的顺序是10、6、4、8、14、12、16。
中序遍历：先访问左子结点，再访问根结点，最后访问右子结点。图2.5中的二叉树的中序遍历的顺序是4、6、8、10、12、14、16。
后序遍历：先访问左子结点，再访问右子结点，最后访问根结点。图2.5中的二叉树的后序遍历的顺序是4、8、6、12、16、14、10。

这3种遍历都有递归和循环两种不同的实现方法，==每一种遍历的递归实现都比循环实现要简捷很多==。

宽度优先遍历：先访问树的第一层结点，再访问树的第二层结点……一直到访问到最下面一层结点。在同一层结点中，以从左到右的顺序依次访问。可以对包括二叉树在内的所有树进行宽度优先遍历。图2.5中的二叉树的宽度优先遍历的顺序是10、6、14、4、8、12、16。

相关的面试题: 面试题39“二叉树的深度”、面试题18“树的子结构”、面试题25“二叉树中和为某一值的路径”、面试题6“重建二叉树”、面试题24“二叉树的后序遍历序列”、面试题23“从上到下遍历二叉树”。

二叉搜索树: 二叉树的一种特例。在二叉搜索树中，左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。图2.5中的二叉树就是一棵二叉搜索树。

我们可以平均在 \(O(\log{n})\) 的时间内根据数值在二叉搜索树中找到一个结点。相关面试题: 面试题50“树中两个结点的最低公共祖先”、面试题27“二叉搜索树与双向链表”。

堆和红黑树: 二叉树的另外两个特例。

堆分为最大堆和最小堆。在最大堆中根结点的值最大，在最小堆中根结点的值最小。有很多需要快速找到最大值或者最小值的问题都可以用堆来解决。

红黑树是把树中的结点定义为红、黑两种颜色，并通过规则确保==从根结点到叶结点的最长路径的长度不超过最短路径的两倍==。在C++的STL中，set、multiset、map、multimap等数据结构都是==基于红黑树实现==的。

与堆和红黑树相关的面试题：面试题30“求最小的k个数字”。

面试题6：重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出图2.6所示的二叉树并输出它的头结点。

二叉树结点的定义如下：

2.3.5 栈和队列

栈在计算机领域被广泛应用。例如，操作系统会给每个线程创建一个栈，用以存储函数调用时各个函数的参数、返回地址、临时变量等。

栈的特点是后进先出 (FILO).

栈通常不考虑排序，也就是需要\(O(n)\)的时间来寻找最值。如果想要在\(O(1)\)的时间内找到最值，需要特殊的设计 (见面试题21)。

队列是另一种重要的结构。其特点是先进先出 (FIFO).

栈和队列针锋相对又相互联系。

面试题7：用两个栈实现队列

2.4 算法和数据操作

排序和查找是面试时考察算法的重点。我们应该熟记二分查找、归并排序、快速排序的代码。

很多算法都可以以循环和递归两种方式来实现。通常，基于递归的实现会比较简洁，但性能一般不如循环的实现。

位运算也是一种特殊的算法，是把数字表示为二进制之后对0和1进行操作。它并不复杂，一共只有与、或、异或、左移、右移5种位运算。

2.4.1 查找和排序

查找相较简单，包括顺序查找、二分查找、哈希表查找和二叉排序树查找。在面试时，必须信手拈来写得出二分查找的代码。相关面试题: 面试题38，面试题8.

面试小提示：如果题目要求「在排序 (或者部分排序) 的数组中查找一个数字或者统计某个数字的出现次数」，则可以尝试使用二分查找。

哈希表和二叉排序树的查找的重点在于数据结构而不是算法。

哈希表的优点是能够在\(O(1)\)内查找某元素，但缺点在于需要额外的空间。相关面试题: 面试题35.

二叉排序树查找算法的对应数据结构是二叉搜索树。相关面试题: 面试题24，面试题27.

排序比查找复杂一些，常见的包括插入排序、冒泡排序、归并排序、快速排序等。面试官常要求应聘者比较不同算法的优劣。因此一定要对各种排序算法的特点烂熟于心，能够从额外空间消耗、平均时间复杂度、最差时间复杂度等方面去比较。

很多面试官要求应聘者写出快速排序的代码。其关键在于在数组中选择一个数字，然后把数组中的数字分为两个部分，比选择的数字小的移到数组左边，比选择的数字大的移到数组右边。这个函数的实现如下：

int Partition(int []data, int length, int start, int end)
{
    if (data == NULL || length <= 0 || start < 0 || end >= length)
        throw new std::exception("Invalid Parameters");
    
    int index = RandomInRange(start, end);
    Swap(&data[index], &data[end]);
    
    int small = start - 1;
    for (index = start; index < end; ++ index)
    {
        if(data[index] < data[end])
        {
            ++ small;
            if(small != index)
                Swap(&data[index], &data[small]);
        }
    }
    
    ++small;
    Swap(&data[index], &data[small]);
    
    return small;
}

第二章 面试需要的基础知识 (下)