2.4 算法和数据操作

和数据结构一样，考查算法的面试题也备受面试官的青睐。有很多算法都可以用递归和循环两种不同的方式实现。通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。在面试的时候，我们可以根据题目的特点，甚至可以和面试官讨论选择合适的方法编程。

通常排序和查找是面试时考查算法的重点。在准备面试的时候，我们应该重点掌握二分查找、归并排序和快速排序，做到能随时正确、完整地写出它们的代码。

如果面试题要求在二维数组（可能具体表现为迷宫或者棋盘等）上搜索路径，那么我们可以尝试用回溯法。通常回溯法很适合用递归的代码实现。只有当面试官限定不可以用递归实现的时候，我们再考虑用栈来模拟递归的过程。

如果面试题是求某个问题的最优解，并且该问题可以分为多个子问题，那么我们可以尝试用动态规划。在用自上而下的递归思路去分析动态规划问题的时候，我们会发现子问题之间存在重叠的更小的子问题。为了避免不必要的重复计算，我们用自下而上的循环代码来实现，也就是把子问题的最优解先算出来并用数组（一般是一维或者二维数组）保存下来，接下来基于子问题的解计算大问题的解。

如果我们告诉面试官动态规划的思路之后，面试官还在提醒说在分解子问题的时候是不是存在某个特殊的选择，如果采用这个特殊的选择将一定能得到最优解，那么，通常面试官这样的提示意味着该面试题可能适用于贪婪算法。当然，面试官也会要求应聘者证明贪婪选择的确最终能够得到最优解。

位运算可以看成一类特殊的算法，它是把数字表示成二进制之后对0和1的操作。由于位运算的对象为二进制数字，所以不是很直观，但掌握它也不难，因为总共只有与、或、异或、左移和右移5种位运算。

2.4.1 递归和循环

如果我们需要重复地多次计算相同的问题，则通常可以选择用递归或者循环两种不同的方法。递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。比如求1+2++n，我们可以用递归或者循环两种方式求出结果。对应的代码如下：

int AddFrom1ToN_Recursive(int n)

{

return n <= 0 ? 0 : n + AddFrom1ToN_Recursive(n - 1);

}

int AddFrom1ToN_Iterative(int n)

{

int result = 0;

for(int i = 1; i <= n; ++ i)

result += i;

return result;

}

通常递归的代码会比较简洁。在上面的例子中，递归的代码只有一条语句，而循环则需要4条语句。在树的前序、中序、后序遍历算法的代码中，递归的实现明显要比循环简单得多。在面试的时候，如果面试官没有特别的要求，则应聘者可以尽量多采用递归的方法编程。

面试小提示：

通常基于递归实现的代码比基于循环实现的代码要简洁很多，更加容易实现。如果面试官没有特殊要求，则应聘者可以优先采用递归的方法编程。

递归虽然有简洁的优点，但它同时也有显著的缺点。递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。

另外，递归中有可能很多计算都是重复的，从而对性能带来很大的负面影响。递归的本质是把一个问题分解成两个或者多个小问题。如果多个小问题存在相互重叠的部分，就存在重复的计算。在面试题10“斐波那契数列”及面试题60“n个骰子的点数”中，我们将详细地分析递归和循环的性能区别。

通常应用动态规划解决问题时我们都是用递归的思路分析问题，但由于递归分解的子问题中存在大量的重复，因此我们总是用自下而上的循环来实现代码。我们将在面试题14“剪绳子”、面试题47“礼物的最大价值”及面试题48“最长不含重复字符的子字符串”中详细讨论如何用递归分析问题并基于循环写代码。

除效率之外，递归还有可能引起更严重的问题：调用栈溢出。在前面的分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。在上述例子中，如果输入的参数比较小，如10，则它们都能返回结果55。但如果输入的参数很大，如5000，那么递归代码在运行的时候就会出错，但运行循环的代码能得到正确的结果12502500。

面试题10：斐波那契数列

题目一：求斐波那契数列的第n项。

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：

效率很低的解法，挑剔的面试官不会喜欢

很多C语言教科书在讲述递归函数的时候，都会用斐波那契数列作为例子，因此很多应聘者对这道题的递归解法都很熟悉。他们看到这道题的时候心中会忍不住一阵窃喜，因为他们能很快写出如下代码：

long long Fibonacci(unsigned int n)

{

if(n <= 0)

return 0;

if(n == 1)

return 1;

return Fibonacci(n - 1) + Fibonacci(n - 2);

}

我们的教科书上反复用这个问题来讲解递归函数，并不能说明递归的解法最适合这道题目。面试官会提示我们上述递归的解法有很严重的效率问题并要求我们分析原因。

我们以求解f(10)为例来分析递归的求解过程。想求得f(10)，需要先求得f(9)和f(8)。同样，想求得f(9)，需要先求得f(8)和f(7)……我们可以用树形结构来表示这种依赖关系，如图2.11所示。

图2.11 基于递归求斐波那契数列的第10项的调用过程

我们不难发现，在这棵树中有很多节点是重复的，而且重复的节点数会随着n的增大而急剧增加，这意味着计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。读者不妨求斐波那契数列的第100项试试，感受一下这样递归会慢到什么程度。

面试官期待的实用解法

其实改进的方法并不复杂。上述递归代码之所以慢，是因为重复的计算太多，我们只要想办法避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来，在下次需要计算的时候我们先查找一下，如果前面已经计算过就不用再重复计算了。

更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，再根据f(1)和f(2)算出f(3)……以此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)。实现代码如下：

long long Fibonacci(unsigned n)

{

int result[2] = {0, 1};

if(n < 2)

return result[n];

long long fibNMinusOne = 1;

long long fibNMinusTwo = 0;

long long fibN = 0;

for(unsigned int i = 2; i <= n; ++ i)

{

fibN = fibNMinusOne + fibNMinusTwo;

fibNMinusTwo = fibNMinusOne;

fibNMinusOne = fibN;

}

return fibN;

}

时间复杂度O(logn)但不够实用的解法

通常面试到这里也就差不多了，尽管我们还有比这更快的O(logn)算法。由于这种算法需要用到一个很生僻的数学公式，因此很少有面试官会要求我们掌握。不过以防不时之需，我们还是简要介绍一下这种算法。

在介绍这种方法之前，我们先介绍一个数学公式：

这个公式用数学归纳法不难证明，感兴趣的读者不妨自己证明一下。有了这个公式，我们只需要求得矩阵即可得到f(n)。现在的问题转换为如何求矩阵的乘方。如果只是简单地从0开始循环，n次方需要n次运算，则其时间复杂度仍然是O(n)，并不比前面的方法快。但我们可以考虑乘方的如下性质：

从上面的公式中我们可以看出，我们想求得n次方，就要先求得n/2次方，再把n/2次方的结果平方一下即可。这可以用递归的思路实现。

由于很少有面试官要求编程实现这种思路，本书中不再列出完整的代码，感兴趣的读者请参考附带的源代码。不过这种基于递归用O(logn)的时间求得n次方的算法却值得我们重视。我们在面试题16“数值的整数次方”中再详细讨论这种算法。

解法比较

用不同的方法求解斐波那契数列的时间效率大不相同。第一种基于递归的解法虽然直观但时间效率很低，在实际软件开发中不会用这种方法，也不可能得到面试官的青睐。第二种方法把递归的算法用循环实现，极大地提高了时间效率。第三种方法把求斐波那契数列转换成求矩阵的乘方，是一种很有创意的算法。虽然我们可以用O(logn)求得矩阵的n次方，但由于隐含的时间常数较大，很少会有软件采用这种算法。另外，实现这种解法的代码也很复杂，不太适合面试。因此第三种方法不是一种实用的算法，不过应聘者可以用它来展示自己的知识面。

除了面试官直接要求编程实现斐波那契数列，还有不少面试题可以看成斐波那契数列的应用。

题目二：青蛙跳台阶问题。

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，那就有两种跳法：一种是分两次跳，每次跳1级；另一种就是一次跳2级。

接着我们再来讨论一般情况。我们把n级台阶时的跳法看成n的函数，记为f(n)。当n>2时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1)；二是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同跳法的总数f(n)=f(n-1)+f(n-2)。分析到这里，我们不难看出这实际上就是斐波那契数列了。

源代码：

本题完整的源代码：

https://github.com/zhedahht/CodingInterviewChinese2/tree/master/10_ Fibonacci

测试用例：

功能测试（如输入3、5、10等）。

边界值测试（如输入0、1、2）。

性能测试（输入较大的数字，如40、50、100等）。

本题考点：

考查应聘者对递归、循环的理解及编码能力。

考查应聘者对时间复杂度的分析能力。

如果面试官采用的是青蛙跳台阶的问题，那么同时还在考查应聘者的数学建模能力。

本题扩展：

在青蛙跳台阶的问题中，如果把条件改成：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？我们用数学归纳法可以证明f(n)=2n1。

相关题目：

我们可以用2×1（图2.12的左边）的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2×1的小矩形无重叠地覆盖一个2×8的大矩形（图2.12的右边），总共有多少种方法？

图2.12 一个2×1的矩形和2×8的矩形

我们先把2×8的覆盖方法记为f(8)。用第一个2×1的小矩形去覆盖大矩形的最左边时有两种选择：竖着放或者横着放。当竖着放的时候，右边还剩下2×7的区域，这种情形下的覆盖方法记为f(7)。接下来考虑横着放的情况。当2×1的小矩形横着放在左上角的时候，左下角必须和横着放一个2×1的小矩形，而在右边还剩下2×6的区域，这种情形下的覆盖方法记为f(6)，因此f(8)= f(7)+f(6)。此时我们可以看出，这仍然是斐波那契数列。

2.4.2 查找和排序

查找和排序都是在程序设计中经常用到的算法。查找相对而言较为简单，不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。在面试的时候，不管是用循环还是用递归，面试官都期待应聘者能够信手拈来写出完整正确的二分查找代码，否则可能连继续面试的兴趣都没有。面试题11“旋转数组的最小数字”和面试题53“在排序数组中查找数字”都可以用二分查找算法解决。

面试小提示：

如果面试题是要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，那么我们都可以尝试用二分查找算法。

哈希表和二叉排序树查找的重点在于考查对应的数据结构而不是算法。哈希表最主要的优点是我们利用它能够在O(1)时间内查找某一元素，是效率最高的查找方式；但其缺点是需要额外的空间来实现哈希表。面试题50“第一个只出现一次的字符”就是用哈希表的特性来实现高效查找的。与二叉排序树查找算法对应的数据结构是二叉搜索树，我们将在面试题33“二叉搜索树的后序遍历序列”和面试题36“二叉搜索树与双向链表”中详细介绍二叉搜索树的特点。

排序比查找要复杂一些。面试官会经常要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。强烈建议应聘者在准备面试的时候，一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。需要特别强调的是，很多公司的面试官喜欢在面试环节要求应聘者写出快速排序的代码。应聘者不妨自己写一个快速排序的函数并用各种数据进行测试。当测试都通过之后，再和经典的实现进行比较，看看有什么区别。

实现快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。这个函数可以如下实现：

int Partition(int data[], int length, int start, int end)

{

if(data == nullptr || 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[small], &data[end]);

return small;

}

函数RandomInRange用来生成一个在start和end之间的随机数，函数Swap的作用是用来交换两个数字。接下来我们可以用递归的思路分别对每次选中的数字的左右两边排序。下面就是递归实现快速排序的参考代码：

void QuickSort(int data[], int length, int start, int end)

{

if(start == end)

return;

int index = Partition(data, length, start, end);

if(index > start)

QuickSort(data, length, start, index - 1);

if(index < end)

QuickSort(data, length, index + 1, end);

}

对一个长度为n的数组排序，只需把start设为0、把end设为n-1，调用函数QuickSort即可。

在前面的代码中，函数Partition除了可以用在快速排序算法中，还可以用来实现在长度为n的数组中查找第k大的数字。面试题39“数组中出现次数超过一半的数字”和面试题40“最小的k个数”都可以用这个函数来解决。

不同的排序算法适用的场合也不尽相同。快速排序虽然总体的平均效率是最好的，但也不是任何时候都是最优的算法。比如数组本身已经排好序了，而每一轮排序的时候都以最后一个数字作为比较的标准，此时快速排序的效率只有O(n2)。因此，在这种场合快速排序就不是最优的算法。在面试的时候，如果面试官要求实现一个排序算法，那么应聘者一定要问清楚这个排序应用的环境是什么、有哪些约束条件，在得到足够多的信息之后再选择最合适的排序算法。下面来看一个面试的片段。

面试官：请实现一个排序算法，要求时间效率为O(n)。

应聘者：对什么数字进行排序，有多少个数字？

面试官：我们想对公司所有员工的年龄排序。我们公司总共有几万名员工。

应聘者：也就是说数字的大小是在一个较小的范围之内的，对吧？

面试官：嗯，是的。

应聘者：可以使用辅助空间吗？

面试官：看你用多少辅助内存。只允许使用常量大小辅助空间，不得超过O(n)。

在面试的时候应聘者不要怕问面试官问题，只有多提问，应聘者才有可能明了面试官的意图。在上面的例子中，该应聘者通过几个问题就弄清楚了需排序的数字在一个较小的范围内，并且可以用辅助内存。知道了这些限制条件，就不难写出如下代码了：

void SortAges(int ages[], int length)

{

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

return;

const int oldestAge = 99;

int timesOfAge[oldestAge + 1];

for(int i = 0; i <= oldestAge; ++ i)

timesOfAge[i] = 0;

for(int i = 0; i < length; ++ i)

{

int age = ages[i];

if(age < 0 || age > oldestAge)

throw new std::exception("age out of range.");

++ timesOfAge[age];

}

int index = 0;

for(int i = 0; i <= oldestAge; ++ i)

{

for(int j = 0; j < timesOfAge[i]; ++ j)

{

ages[index] = i;

++ index;

}

}

}

公司员工的年龄有一个范围。在上面的代码中，允许的范围是0～99岁。数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次，就在数组ages里设置几次该年龄，这就相当于给数组ages排序了。该方法用长度100的整数数组作为辅助空间换来了O(n)的时间效率。

面试题11：旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

这道题最直观的解法并不难，从头到尾遍历数组一次，我们就能找出最小的元素。这种思路的时间复杂度显然是O(n)。但是这种思路没有利用输入的旋转数组的特性，肯定达不到面试官的要求。

我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中我们可以用二分查找法实现O(logn)的查找。本题给出的数组在一定程度上是排序的，因此我们可以试着用二分查找法的思路来寻找这个最小的元素。

和二分查找法一样，我们用两个指针分别指向数组的第一个元素和最后一个元素。按照题目中旋转的规则，第一个元素应该是大于或者等于最后一个元素的（这其实不完全对，还有特例，后面再加以讨论）。

接着我们可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组。

同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素，这样也可以缩小寻找的范围。移动之后的第二个指针仍然位于后面的递增子数组。

不管是移动第一个指针还是第二个指针，查找范围都会缩小到原来的一半。接下来我们再用更新之后的两个指针重复做新一轮的查找。

按照上述思路，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。

以前面的数组{3, 4, 5, 1, 2}为例，我们先把第一个指针指向第0个元素，把第二个指针指向第4个元素，如图2.13（a）所示。位于两个指针中间（在数组中的下标是2）的数字是5，它大于第一个指针指向的数字。因此中间数字5一定位于第一个递增子数组，并且最小的数字一定位于它的后面。因此我们可以移动第一个指针，让它指向数组的中间，如图2.13（b）所示。

此时位于这两个指针中间（在数组中的下标是3）的数字是1，它小于第二个指针指向的数字。因此这个中间数字1一定位于第二个递增字数组，并且最小的数字一定位于它的前面或者它自己就是最小的数字。因此我们可以移动第二个指针，让它指向两个指针中间的元素，即下标为3的元素，如图2.13（c）所示。

图2.13 在数组{3, 4, 5, 1, 2}中查找最小值的过程

注：旋转数组中包含两个递增排序的子数组，有阴影的是第二个子数组。（a）把P1指向数组的第一个数字，P2指向数组的最后一个数字。由于P1和P2中间的数字5大于P1指向的数字，中间的数字在第一个子数组中。下一步把P1指向中间的数字。（b）P1和P2中间的数字1小于P2指向的数字，中间的数字在第二个子数组中。下一步把P2指向中间的数字。（c）P1和P2指向两个相邻的数字，则P2指向的是数组中的最小数字。

此时两个指针的距离是1，表明第一个指针已经指向第一个递增子数组的末尾，而第二个指针指向第二个递增子数组的开头。第二个子数组的第一个数字就是最小的数字，因此第二个指针指向的数字就是我们查找的结果。

基于这个思路，我们可以写出如下代码：

int Min(int* numbers, int length)

{

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

throw new std::exception("Invalid parameters");

int index1 = 0;

int index2 = length - 1;

int indexMid = index1;

while(numbers[index1] >= numbers[index2])

{

if(index2 - index1 == 1)

{

indexMid = index2;

break;

}

indexMid = (index1 + index2) / 2;

if(numbers[indexMid] >= numbers[index1])

index1 = indexMid;

else if(numbers[indexMid] <= numbers[index2])

index2 = indexMid;

}

return numbers[indexMid];

}

前面我们提到，在旋转数组中，由于是把递增排序数组前面的若干个数字搬到数组的后面，因此第一个数字总是大于或者等于最后一个数字。但按照定义还有一个特例：如果把排序数组的前面的0个元素搬到最后面，即排序数组本身，这仍然是数组的一个旋转，我们的代码需要支持这种情况。此时，数组中的第一个数字就是最小的数字，可以直接返回。这就是在上面的代码中，把indexMid初始化为index1的原因。一旦发现数组中第一个数字小于最后一个数字，表明该数组是排序的，就可以直接返回第一个数字。

上述代码是否就完美了呢？面试官会告诉我们其实不然。他将提示我们再仔细分析下标为index1和index2（index1和index2分别与图2.13中P1和P2相对应）的两个数相