6.3 知识迁移能力

所谓学习能力，很重要的一点就是根据已经掌握的知识、技术，能够迅速学习、理解新的技术并运用到实际工作中去。大部分新的技术都不是凭空产生的，而是在已有技术的基础上发展起来的。这就要求我们能够把对已有技术的理解迁移到学习新技术的过程中去，也就是要具备很强的知识迁移能力。以学习编程语言为例，如果全面理解了C++的面向对象的思想，那么学习下一门面向对象的语言Java就不会很难；在深刻理解了Java的垃圾回收机制之后，再去学习另一门托管语言比如C#，也会很容易。

面试官考查应聘者知识迁移能力的一种方法是把经典的问题稍作变换。这时候面试官期待应聘者能够找到和经典问题的联系，并从中受到启发，把解决经典问题的思路迁移过来解决新的问题。比如，如果遇到面试题53“在排序数组中查找数字”，我们看到“排序数组”就可以想到二分查找算法。通常二分查找算法用来在一个排序数组中查找一个数字。我们可以把二分查找算法的思想迁移过来稍作变换，用二分查找算法在排序数组中查找重复数字的第一个和最后一个，从而得到数字在数组中出现的次数。

面试官考查应聘者知识迁移能力的另一种方法就是先问一个简单的问题，在应聘者解答完这个简单的问题之后，再追问一个相关的同时难度也更大的问题。这时候面试官希望应聘者能够总结前面解决简单问题的经验，把前面的思路、方法迁移过来。比如在面试题56“数组中数字出现的次数”中，面试官先问一个简单的问题，即数组中只有一个数字只出现一次的情况。在应聘者想出用异或的办法找到这个只出现一次的数字之后，他再追问如果数组中有两个数字只出现一次，那么该怎么找出这两个数字？这时候应聘者要从前面的思路中得到启发：既然有办法找到数组中只出现一次的一个数字，那么当数组中有两个数字只出现一次的时候，我们就可以把整个数组一分为二，每个子数组中包含一个只出现一次的数字，这样我们就能在两个子数组中分别找到那两个只出现一次的数字。接下来我们就可以集中精力去想办法把数组一分为二，这样就能找到解决问题的窍门，整道题目的难度系数就降低了不少。

知识迁移能力的一种通俗的说法是“举一反三”的能力。我们在去面试之前，通常都会看一些经典的面试题。然而题目总是做不完的，我们不可能把所有的面试题都准备一遍。因此，更重要的是每做一道面试题的时候，都要总结这道题的解法有什么特点，有哪些思路是可以应用到同类型的题目中去的。比如，为了解决面试题“翻转单词顺序”，我们先翻转整个句子的所有字符，再分别翻转每个单词中的字符。这样多次翻转字符的思路也可以运用到面试题“左旋转字符串”中（详见面试题58）。在解决面试题38“字符串的排列”之后，我们发现“八皇后问题”其实归根结底就是数组的排列问题。本书中很多章节在分析了一道题之后，列举了与这道题相关的题目，读者可以通过分析这些题目的相关性来提高举一反三的能力。

面试题53：在排序数组中查找数字

题目一：数字在排序数组中出现的次数。

统计一个数字在排序数组中出现的次数。例如，输入排序数组{1, 2, 3, 3, 3, 3, 4, 5}和数字3，由于3在这个数组中出现了4次，因此输出4。

既然输入的数组是排序的，那么我们就能很自然地想到用二分查找算法。在题目给出的例子中，我们可以先用二分查找算法找到一个3。由于3可能出现多次，因此我们找到的3的左右两边可能都有3，于是在找到的3的左右两边顺序扫描，分别找出第一个3和最后一个3。因为要查找的数字在长度为n的数组中有可能出现O(n)次，所以顺序扫描的时间复杂度是O(n)。因此，这种算法的效率和直接从头到尾顺序扫描整个数组统计3出现的次数的方法是一样的。显然，面试官不会满意这个算法，他会提示我们还有更快的算法。

接下来我们思考如何更好地利用二分查找算法。假设我们要统计数字k在排序数组中出现的次数。在前面的算法中，时间主要消耗在如何确定重复出现的数字的第一个k和最后一个k的位置上，有没有可能用二分查找算法直接找到第一个k及最后一个k呢？

我们先分析如何用二分查找算法在数组中找到第一个k。二分查找算法总是先拿数组中间的数字和k作比较。如果中间的数字比k大，那么k只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。如果中间的数字比k小，那么k只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。如果中间数字的前面一个数字不是k，那么此时中间的数字刚好就是第一个k；如果中间数字的前面一个数字也是k，那么第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。

基于这种思路，我们可以很容易地写出递归的代码找到排序数组中的第一个k。下面是一段参考代码：

int GetFirstK(int* data, int length, int k, int start, int end)

{

if(start > end)

return -1;

int middleIndex = (start + end) / 2;

int middleData = data[middleIndex];

if(middleData == k)

{

if((middleIndex > 0 && data[middleIndex - 1] != k)

|| middleIndex == 0)

return middleIndex;

else

end = middleIndex - 1;

}

else if(middleData > k)

end = middleIndex - 1;

else

start = middleIndex + 1;

return GetFirstK(data, length, k, start, end);

}

在函数GetFirstK中，如果数组中不包含数字k，那么返回-1；如果数组中包含至少一个k，那么返回第一个k在数组中的下标。

我们可以用同样的思路在排序数组中找到最后一个k。如果中间数字比k大，那么k只能出现在数组的前半段。如果中间数字比k小，那么k只能出现在数组的后半段。如果中间数字等于k呢？我们需要判断这个k是不是最后一个k，也就是中间数字的下一个数字是不是也等于k。如果下一个数字不是k，则中间数字就是最后一个k；否则下一轮我们还是要在数组的后半段中去查找。我们同样可以基于递归写出如下代码：

int GetLastK(int* data, int length, int k, int start, int end)

{

if(start > end)

return -1;

int middleIndex = (start + end) / 2;

int middleData = data[middleIndex];

if(middleData == k)

{

if((middleIndex < length - 1 && data[middleIndex + 1] != k)

|| middleIndex == length - 1)

return middleIndex;

else

start = middleIndex + 1;

}

else if(middleData < k)

start = middleIndex + 1;

else

end = middleIndex - 1;

return GetLastK(data, length, k, start, end);

}

和函数GetFirstK类似，如果数组中不包含数字k，那么GetLastK返回-1；否则返回最后一个k在数组中的下标。

在分别找到第一个k和最后一个k的下标之后，我们就能计算出k在数组中出现的次数。相应的代码如下：

int GetNumberOfK(int* data, int length, int k)

{

int number = 0;

if(data != nullptr && length > 0)

{

int first = GetFirstK(data, length, k, 0, length - 1);

int last = GetLastK(data, length, k, 0, length - 1);

if(first > -1 && last > -1)

number = last - first + 1;

}

return number;

}

在上述代码中，GetFirstK和GetLastK都是用二分查找算法在数组中查找一个合乎要求的数字的，它们的时间复杂度都是O(logn)，因此GetNumberOfK的总的时间复杂度也只有O(logn)。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/53_01_NumberOfK

测试用例：

功能测试（数组中包含要查找的数字；数组中没有要查找的数字；要查找的数字在数组中出现一次/多次）。

边界值测试（查找数组中的最大值、最小值；数组中只有一个数字）。

特殊输入测试（表示数组的指针为nullptr指针）。

题目二：0～n1中缺失的数字。

一个长度为n1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n1之内。在范围0～n1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

这个问题有一个直观的解决方案。我们可以先用公式n(n1)/2求出数字0～n1的所有数字之和，记为s1。接着求出数组中所有数字的和，记为s2。那个不在数组中的数字就是s1s2的差。这种解法需要O(n)的时间求数组中所有数字的和。显然，该解法没有有效利用数组是递增排序的这一特点。

因为0～n1这些数字在数组中是排序的，因此数组中开始的一些数字与它们的下标相同。也就是说，0在下标为0的位置，1在下标为1的位置，以此类推。如果不在数组中的那个数字记为m，那么所有比m小的数字的下标都与它们的值相同。

由于m不在数组中，那么m+1处在下标为m的位置，m+2处在下标为m+1的位置，以此类推。我们发现m正好是数组中第一个数值和下标不相等的下标，因此这个问题转换成在排序数组中找出第一个值和下标不相等的元素。

我们可以基于二分查找的算法用如下过程查找：如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着这个中间的数字正好是第一个值和下标不相等的元素，它的下标就是在数组中不存在的数字；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标不相等，这意味着下一轮查找我们只需要在左半边查找即可。

下面是基于二分查找算法的参考代码：

int GetMissingNumber(const int* numbers, int length)

{

if(numbers == nullptr || length <= 0)

return -1;

int left = 0;

int right = length - 1;

while(left <= right)

{

int middle = (right + left) >> 1;

if(numbers[middle] != middle)

{

if(middle == 0 || numbers[middle - 1] == middle - 1)

return middle;

right = middle - 1;

}

else

left = middle + 1;

}

if(left == length)

return length;

// 无效的输入，比如数组不是按要求排序的，

// 或者有数字不在0～n1范围之内

return -1;

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/53_02_MissingNumber

测试用例：

功能测试（缺失的数字位于数组的开始、中间或者末尾）。

边界值测试（数组中只有一个数字0）

特殊输入测试（表示数组的指针为nullptr指针）。

题目三：数组中数值和下标相等的元素。

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{3, 1, 1, 3, 5}中，数字3和它的下标相等。

我们很容易就能想到最直观的解法：从头到尾依次扫描数组中的数字，并逐一检验数字是不是和下标相等。显然，这种算法的时间复杂度是O(n)。

由于数组是单调递增排序的，因此我们可以尝试用二分查找算法来进行优化。假设我们某一步抵达数组中的第i个数字。如果我们很幸运，该数字的值刚好也是i，那么我们就找到了一个数字和其下标相等。

那么当数字的值和下标不相等的时候该怎么办呢？假设数字的值为m。我们先考虑m大于i的情形，即数字的值大于它的下标。由于数组中的所有数字都唯一并且单调递增，那么对于任意大于0的k，位于下标i+k的数字的值大于或等于m+k。另外，因为m>i，所以m+k>i+k。因此，位于下标i+k的数字的值一定大于它的下标。这意味着如果第i个数字的值大于i，那么它右边的数字都大于对应的下标，我们都可以忽略。下一轮查找我们只需要从它左边的数字中查找即可。

数字的值m小于它的下标i的情形和上面类似。它左边的所有数字的值都小于对应的下标，我们也可以忽略。感兴趣的读者请自己证明。

由于我们在每一步查找时都可以把查找的范围缩小一半，这是典型的二分查找的过程。下面是基于二分查找的参考代码：

int GetNumberSameAsIndex(const int* numbers, int length)

{

if(numbers == nullptr || length <= 0)

return -1;

int left = 0;

int right = length - 1;

while(left <= right)

{

int middle = left + ((right - left) >> 1);

if(numbers[middle] == middle)

return middle;

if(numbers[middle] > middle)

right = middle - 1;

else

left = middle + 1;

}

return -1;

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/53_03_ IntegerIdenticalToIndex

测试用例：

功能测试（数组中包含或者不包含数值和下标相等的元素）。

边界值测试（数组中只有一个数字；数值和下标相等的元素位于数组的开头或者结尾）。

特殊输入测试（表示数组的指针为nullptr指针）。

本题考点：

考查应聘者的知识迁移能力。我们都知道，二分查找算法可以用来在排序数组中查找一个数字。应聘者如果能够运用知识迁移能力，把问题转换成用二分查找算法在排序数组中查找某些特定的数字，那么这些问题也就解决了一大半。

考查应聘者对二分查找算法的理解程度。这道题实际上是二分查找算法的加强版。只有对二分查找算法有着深刻的理解，应聘者才有可能解决这个问题。

面试题54：二叉搜索树的第k大节点

题目：给定一棵二叉搜索树，请找出其中第k大的节点。例如，在图6.1中的二叉搜索树里，按节点数值大小顺序，第三大节点的值是4。

图6.1 一棵有7个节点的二叉搜索树，其中按节点数值大小顺序，第三大节点的值是4

如果按照中序遍历的顺序遍历一棵二叉搜索树，则遍历序列的数值是递增排序的。例如，图6.1中二叉搜索树的中序遍历序列是{2, 3, 4, 5, 6, 7, 8}。因此，只需要用中序遍历算法遍历一棵二叉搜索树，我们就很容易找出它的第k大节点。

这道题实质上考查应聘者对中序遍历的理解。只要熟练掌握了中序遍历，应聘者很快就能写出如下代码：

BinaryTreeNode* KthNode(BinaryTreeNode* pRoot, unsigned int k)

{

if(pRoot == nullptr || k == 0)

return nullptr;

return KthNodeCore(pRoot, k);

}

BinaryTreeNode* KthNodeCore(BinaryTreeNode* pRoot, unsigned int& k)

{

BinaryTreeNode* target = nullptr;

if(pRoot->m_pLeft != nullptr)

target = KthNodeCore(pRoot->m_pLeft, k);

if(target == nullptr)

{

if(k == 1)

target = pRoot;

k--;

}

if(target == nullptr && pRoot->m_pRight != nullptr)

target = KthNodeCore(pRoot->m_pRight, k);

return target;

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/54_ KthNodeInBST

测试用例：

功能测试（各种形态不同的二叉搜索树）。

边界值测试（输入k为0、1、二叉搜索树的节点数、二叉搜索树的节点数加1）。

特殊输入测试（指向二叉搜索树根节点的指针为nullptr指针）。

本题考点：

考查应聘者的知识迁移能力。面试官期待应聘者能够运用中序遍历算法来解决这道面试题。

考查应聘者对二叉搜索树和中序遍历的特点的理解。如果应聘者理解二叉搜索树的中序遍历序列是递增的，那么他/她很容易就能找出第k大的节点。

面试题55：二叉树的深度

题目一：二叉树的深度。

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

二叉树的节点定义如下：

struct BinaryTreeNode

{

int m_nValue;

BinaryTreeNode* m_pLeft;

BinaryTreeNode* m_pRight;

};

例如，在图6.2中的二叉树的深度为4，因为它从根节点到叶节点最长的路径包含4个节点（从根节点1开始，经过节点2和节点5，最终到达叶节点7）。

图6.2 深度为4的二叉树

在本题中，面试官给出了一种树的深度的定义，我们可以根据这个定义去得到树的所有路径，也就能得到最长的路径及它的长度。在面试题34“二叉树中和为某一值的路径”中我们详细讨论了如何记录树中的路径。这种思路的代码量比较大，我们可以尝试更加简洁的方法。

我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个节点，那么它的深度为1。如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样，如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树，那么该树的深度就是其左、右子树深度的较大值再加1。比如，在图6.2所示的二叉树中，根节点为1的树有左、右两棵子树，其左、右子树的根节点分别为节点2和节点3。根节点为2的左子树的深度为3，而根节点为3的右子树的深度为2，因此，根节点为1的树的深度就是4。

这种思路用递归的方法很容易实现，只需对遍历的代码稍作修改即可。参考代码如下：

int TreeDepth(BinaryTreeNode* pRoot)

{

if(pRoot == nullptr)

return 0;

int nLeft = TreeDepth(pRoot->m_pLeft);

int nRight = TreeDepth(pRoot->m_pRight);

return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);

}

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/55_01_TreeDepth

测试用例：

功能测试（输入普通的二叉树；二叉树中所有节点都没有左/右子树）。

特殊输入测试（二叉树只有一个节点；二叉树的头节点为nullptr指针）。

只要应聘者对二叉树这一数据结构很熟悉，就能很快写出上面的代码。如果公司对编程能力有较高的要求，那么面试官可能会追加一个与前面问题相关但难度更大的问题。

题目二：平衡二叉树。

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左、右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如，图6.2中的二叉树就是一棵平衡二叉树。

需要重复遍历节点多次的解法，简单但不足以打动面试官

有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一种思路：在遍历树的每个节点的时候，调用函数TreeDepth得到它的左、右子树的深度。如果每个节点的左、右子树的深度相差都不超过1，那么按照定义它就是一棵平衡二叉树。这种思路对应的代码如下：

bool IsBalanced(BinaryTreeNode* pRoot)

{

if(pRoot == nullptr)

return true;

int left = TreeDepth(pRoot->m_pLeft);

int right = TreeDepth(pRoot->m_pRight);

int diff = left - right;

if(diff > 1 || diff < -1)

return false;

return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);

}

上面的代码固然简洁，但我们也要注意到由于一个节点会被重复遍历多次，这种思路的时间效率不高。例如，在函数IsBalance中输入图6.2中的二叉树，我们将首先判断根节点（节点1）是不是平衡的。此时我们往函数TreeDepth里输入左子树的根节点（节点2）时，需要遍历节点4、5、7。接下来判断以节点2为根节点的子树是不是平衡树的时候，仍然会遍历节点4、5、7。毫无疑问，重复遍历同一个节点会影响性能。接下来我们寻找不需要重复遍历的算法。

每个节点只遍历一次的解法，正是面试官喜欢的

如果我们用后序遍历的方式遍历二叉树的每个节点，那么在遍历到一个节点之前我们就已经遍历了它的左、右子树。只要在遍历每个节点的时候记录它的深度（某一节点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个节点是不是平衡的。下面是这种思路的参考代码：

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)

{

if(pRoot == nullptr)

{

*pDepth = 0;

return true;

}

int left, right;

if(IsBalanced(pRoot->m_pLeft, &left)

&& IsBalanced(pRoot->m_pRight, &right))

{

int diff = left - right;

if(diff <= 1 && diff >= -1)

{

*pDepth = 1 + (left > right ? left : right);

return true;

}

}

return false;

}

我们只需给上面的函数传入二叉树的根节点及一个表示节点深度的整型变量即可。

bool IsBalanced(BinaryTreeNode* p