第2章 面试需要的基础知识 2.1 面试官谈基础知识 “C++的基础知识，如面向对象的特性、构造函数、析构函数、动态绑定等，能够反映出应聘者是否善于把握问题本质，有没有耐心深入一个问题。另外还有常用的设计模式、UML图等，这些都能体现应聘者是否有软件工程方面的经验。” ——王海波（Autodesk，软件工程师） “对基础知识的考查我特别重视C++中对内存的使用管理。我觉得内存管理是C++程序员特别要注意的，因为内存的使用和管理会影响程序的效率和稳定性。” ——蓝诚（Autodesk，软件工程师） “基础知识反映了一个人的基本能力和基础素质，是以后工作中最核心的能力要求。我一般考查：（1）数据结构和算法；（2）编程能力；（3）部分数学知识，如概率；（4）问题的分析和推理能力。” ——张晓禹（百度，技术经理） “我比较重视四块基础知识：（1）编程基本功（特别喜欢字符串处理这一类的问题）；（2）并发控制；（3）算法、复杂度；（4）语言的基本概念。” ——张珺（百度，高级软件工程师） “我会考查编程基础、计算机系统基础知识、算法以及设计能力。这些是一个软件工程师的最基本的东西，这些方面表现出色的人，我们一般认为是有发展潜力的。” ——韩伟东（盛大，高级研究员） “（1）对OS的理解程度。这些知识对于工作中常遇到的内存管理、文件操作、程序性能、多线程、程序安全等有重要帮助。对于OS理解比较深入的人对于偏底层的工作上手一般比较快。（2）对于一门编程语言的掌握程度。一个热爱编程的人应该会对某种语言有比较深入的了解。通常这样的人对于新的编程语言上手也比较快，而且理解比较深入。（3）常用的算法和数据结构。不了解这些的程序员基本只能写写‘Hello World’。” ——陈黎明（微软，SDE II） 2.2 编程语言 程序员写代码总是基于某一种编程语言，因此技术面试的时候直接或者间接都会涉及至少一种编程语言。在面试的过程中，面试官要么直接问语言的语法，要么让应聘者用一种编程语言写代码解决一个问题，通过写出的代码来判断应聘者对他使用的语言的掌握程度。现在流行的编程语言很多，不同公司开发用的语言也不尽相同。做底层开发比如经常写驱动的人更习惯用C，Linux下有很多程序员用C++开发应用程序，基于Windows的C#项目已经越来越多，跨平台开发的程序员则可能更喜欢Java，随着苹果iPad、iPhone的热销已经有很多程序员投向了Objective C的阵营，同时还有很多人喜欢用脚本语言如Perl、Python开发短小精致的小应用软件。因此，不同公司面试的时候对编程语言的要求也有所不同。每一种编程语言都可以写出一本大部头的书籍，本书限于篇幅不可能面面俱到。本书中所有代码都用C/C++/C#实现，下面简要介绍一些C++/C#常见的面试题。 2.2.1 C++ 国内绝大部分高校都开设C++的课程，因此绝大部分程序员都学过C++，于是C++成了各公司面试的首选编程语言。包括Autodesk在内的很多公司在面试的时候会有大量的C++的语法题，其他公司虽然不直接面试C++的语法，但面试题要求用C++实现算法。因此总的说来，应聘者不管去什么公司求职，都应该在一定程度上掌握C++。 通常语言面试有3种类型。第一种类型是面试官直接询问应聘者对C++概念的理解。这种类型的问题，面试官特别喜欢了解应聘者对C++关键字的理解程度。例如：在C++中，有哪4个与类型转换相关的关键字？这些关键字各有什么特点，应该在什么场合下使用？ 在这种类型的题目中，sizeof是经常被问到的一个概念。比如下面的面试片段，就反复出现在各公司的技术面试中。 面试官：定义一个空的类型，里面没有任何成员变量和成员函数。对该类型求sizeof，得到的结果是多少？ 应聘者：答案是1。 面试官：为什么不是0？ 应聘者：空类型的实例中不包含任何信息，本来求sizeof应该是0，但是当我们声明该类型的实例的时候，它必须在内存中占有一定的空间，否则无法使用这些实例。至于占用多少内存，由编译器决定。Visual Studio中每个空类型的实例占用1字节的空间。 面试官：如果在该类型中添加一个构造函数和析构函数，再对该类型求sizeof，得到的结果又是多少？ 应聘者：和前面一样，还是1。调用构造函数和析构函数只需要知道函数的地址即可，而这些函数的地址只与类型相关，而与类型的实例无关，编译器也不会因为这两个函数而在实例内添加任何额外的信息。 面试官：那如果把析构函数标记为虚函数呢？ 应聘者：++的编译器一旦发现一个类型中有虚拟函数，就会为该类型生成虚函数表，并在该类型的每一个实例中添加一个指向虚函数表的指针。在32位的机器上，一个指针占4字节的空间，因此求sizeof得到4；如果是64位的机器，一个指针占8字节的空间，因此求sizeof则得到8。 面试C/C++的第二种题型就是面试官拿出事先准备好的代码，让应聘者分析代码的运行结果。这种题型选择的代码通常包含比较复杂微妙的语言特性，这要求应聘者对C++考点有着透彻的理解。即使应聘者对考点有一点点模糊，那么最终他得到的结果和实际运行的结果可能就会差距甚远。 比如面试官递给应聘者一张有如下代码的A4打印纸要求他分析编译运行的结果，并提供3个选项：A.编译错误；B.编译成功，运行时程序崩溃；C.编译运行正常，输出10。  在上述代码中，复制构造函数A（A other）传入的参数是A的一个实例。由于是传值参数，我们把形参复制到实参会调用复制构造函数。因此如果允许复制构造函数传值，就会在复制构造函数内调用复制构造函数，就会形成永无休止的递归调用从而导致栈溢出。因此C++的标准不允许复制构造函数传值参数，在Visual Studio和GCC中，都将编译出错。要解决这个问题，我们可以把构造函数修改为A（const A&other），也就是把传值参数改成常量引用。 第三种题型就是要求应聘者写代码定义一个类型或者实现类型中的成员函数。让应聘者写代码的难度自然比让应聘者分析代码要高不少，因为能想明白的未必就能写得清楚。很多考查C++语法的代码题围绕在构造函数、析构函数及运算符重载。比如面试题1“赋值运算符函数”就是一个例子。 为了让大家能顺利地通过C++面试，更重要的是能更好地学习掌握C++这门编程语言，这里推荐几本C++的书，大家可以根据自己的具体情况选择阅读的顺序： ● 《Effective C++》。这本书很适合在面试之前突击C++。这本书列举了使用C++经常出现的问题及解决这些问题的技巧。该书中提到的问题也是面试官很喜欢问的问题。 ● 《C++ Primer》。读完这本书，就会对C++的语法有全面的了解。 ● 《Inside C++ Object Model》。这本书有助于我们深入了解C++对象的内部。读懂这本书后很多C++难题，比如前面的sizeof的问题、虚函数的调用机制等，都会变得很容易。 ● 《The C++ Programming Language》。如果是想全面深入掌握C++，没有哪本书比这本书更适合的了。 面试题1：赋值运算符函数 题目：如下为类型CMyString的声明，请为该类型添加赋值运算符函数。  当面试官要求应聘者定义一个赋值运算符函数时，他会在检查应聘者写出的代码时关注如下几点： ● 是否把返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的引用（即\*this）。只有返回一个引用，才可以允许连续赋值。否则如果函数的返回值是void，应用该赋值运算符将不能做连续赋值。假设有3个CMyString的对象：str1、str2和str3，在程序中语句str1=str2=str3将不能通过编译。 ● 是否把传入的参数的类型声明为常量引用。如果传入的参数不是引用而是实例，那么从形参到实参会调用一次复制构造函数。把参数声明为引用可以避免这样的无谓消耗，能提高代码的效率。同时，我们在赋值运算符函数内不会改变传入的实例的状态，因此应该为传入的引用参数加上const关键字。 ● 是否释放实例自身已有的内存。如果我们忘记在分配新内存之前释放自身已有的空间，程序将出现内存泄露。 ● 是否判断传入的参数和当前的实例（\*this）是不是同一个实例。如果是同一个，则不进行赋值操作，直接返回。如果事先不判断就进行赋值，那么在释放实例自身的内存的时候就会导致严重的问题：当\*this和传入的参数是同一个实例时，那么一旦释放了自身的内存，传入的参数的内存也同时被释放了，因此再也找不到需要赋值的内容了。 经典的解法，适用于初级程序员 当我们完整地考虑了上述4个方面之后，我们可以写出如下的代码：  这是一般C++教材上提供的参考代码。如果接受面试的是应届毕业生或者C++初级程序员，能全面地考虑到前面四点并完整地写出代码，面试官可能会让他通过这轮面试。但如果面试的是C++高级程序员，面试官可能会提出更高的要求。 考虑异常安全性的解法，高级程序员必备 在前面的函数中，我们在分配内存之前先用delete释放了实例m\_pData的内存。如果此时内存不足导致new char抛出异常，m\_pData将是一个空指针，这样非常容易导致程序崩溃。也就是说一旦在赋值运算符函数内部抛出一个异常，CMyString的实例不再保持有效的状态，这就违背了异常安全性（Exception Safety）原则。 要想在赋值运算符函数中实现异常安全性，我们有两种方法。一个简单的办法是我们先用new分配新内容再用delete释放已有的内容。这样只在分配内容成功之后再释放原来的内容，也就是当分配内存失败时我们能确保CMyString的实例不会被修改。我们还有一个更好的办法是先创建一个临时实例，再交换临时实例和原来的实例。下面是这种思路的参考代码：  在这个函数中，我们先创建一个临时实例strTemp，接着把strTemp.m\_pData和实例自身的m\_pData做交换。由于strTemp是一个局部变量，但程序运行到if的外面时也就出了该变量的作用域，就会自动调用strTemp的析构函数，把strTemp.m\_pData所指向的内存释放掉。由于strTemp.m\_pData指向的内存就是实例之前m\_pData的内存，这就相当于自动调用析构函数释放实例的内存。 在新的代码中，我们在CMyString的构造函数里用new分配内存。如果由于内存不足抛出诸如bad\_alloc等异常，我们还没有修改原来实例的状态，因此实例的状态还是有效的，这也就保证了异常安全性。 如果应聘者在面试的时候能够考虑到这个层面，面试官就会觉得他对代码的异常安全性有很深的理解，那么他自然也就能通过这轮面试了。 源代码： 本题完整的源代码详见01\_AssignmentOperator项目。 测试用例： ● 把一个CMyString的实例赋值给另外一个实例。 ● 把一个CMyString的实例赋值给它自己。 ● 连续赋值。 本题考点： ● 考查对C++的基础语法的理解，如运算符函数、常量引用等。 ● 考查对内存泄露的理解。 ● 对高级C++程序员，面试官还将考查应聘者对代码异常安全性的理解。 2.2.2 C# C#是微软在推出新的开发平台.NET时同步推出的编程语言。由于Windows至今仍然是用户最多的操作系统，而.NET又是微软近年来力推的开发平台，因此C#无论在桌面软件还是网络应用的开发上都有着广泛的应用，所以我们也不难理解为什么现在很多基于Windows系统开发的公司都会要求应聘者掌握C#。 C#可以看成是一门以C++为基础发展起来的一种托管语言，因此它的很多关键字甚至语法都和C++很类似。对一个学习过C++编程的程序员而言，他用不了多长时间学习就能用C#来开发软件。然而我们也要清醒地认识到，虽然学习C#与C++相同或者类似的部分很容易，但要掌握并区分两者不同的地方却不是一件很容易的事情。面试官总是喜欢深究我们模棱两可的地方以考查我们是不是真的理解了，因此我们要着重注意C#与C++不同的语法特点。下面的面试片段就是一个例子： 面试官：C++中可以用struct和class来定义类型。这两种类型有什么区别？ 应聘者：如果没有标明成员函数或者成员变量的访问权限级别，在struct中默认的是public，而在class中默认的是private。 面试官：那在C#中呢？ 应聘者：C#和C++不一样。在C#中如果没有标明成员函数或者成员变量的访问权限级别，struct和class中都是private的。struct和class的区别是struct定义的是值类型，值类型的实例在栈上分配内存；而class定义的是引用类型，引用类型的实例在堆上分配内存。 在C#中，每个类型中和C++一样，都有构造函数。但和C++不同的是，我们在C#中可以为类型定义一个Finalizer和Dispose方法以释放资源。Finalizer方法虽然写法与C++的析构函数看起来一样，都是后面跟类型名字，但与C++析构函数的调用时机是确定的不同，C#的Finalizer是在运行时（CLR）做垃圾回收时才会被调用，它的调用时机是由运行时决定的，因此对程序员来说是不确定的。另外，在C#中可以为类型定义一个特殊的构造函数：静态构造函数。这个函数的特点是在类型第一次被使用之前由运行时自动调用，而且保证只调用一次。关于静态构造函数，我们有很多有意思的面试题，比如运行下面的C#代码，输出的结果是什么？  在调用类型B的代码之前先执行B的静态构造函数。静态构造函数先初始化类型的静态变量，再执行函数体内的语句。因此先打印a1再打印a3。接下来执行Bb=newB（），即调用B的普通构造函数。构造函数先初始化成员变量，再执行函数体内的语句，因此先后打印出a2、a4。因此运行上面的代码，得到的结果将是打印出4行，分别是a1、a3、a2、a4。 我们除了要关注C#和C++不同的知识点之外，还要格外关注C#一些特有的功能，比如反射、应用程序域（AppDomain）等。这些概念还相互关联，要花很多时间学习研究才能透彻地理解它们。下面的代码就是一段关于反射和应用程序域的代码，运行它得到的结果是什么？  上述C#代码先创建一个名为NewDomain的应用程序域，并在该域中利用反射机制创建类型A的一个实例和类型B的一个实例。我们注意到类型A是继承自MarshalByRefObject，而B不是。虽然这两个类型的结构一样，但由于基类不同而导致在跨越应用程序域的边界时表现出的行为将大不相同。 先考虑A的情况。由于A继承自MarshalByRefObject，那么a实际上只是在默认的域中的一个代理实例（Proxy），它指向位于NewDomain域中的A的一个实例。当调用a的方法SetNumber时，是在NewDomain域中调用该方法，它将修改NewDomain域中静态变量A.Number的值并设为20。由于静态变量在每个应用程序域中都有一份独立的拷贝，修改NewDomain域中的静态变量A.Number对默认域中的静态变量A.Number没有任何影响。由于Console.WriteLine是在默认的应用程序域中输出A.Number，因此输出仍然是10。 接着讨论B。由于B只是从Object继承而来的类型，它的实例穿越应用程序域的边界时，将会完整地复制实例。因此在上述代码中，我们尽管试图在NewDomain域中生成B的实例，但会把实例b复制到默认的应用程序域。此时调用方法b.SetNumber也是在缺省的应用程序域上进行，它将修改默认的域上的A.Number并设为20。再在默认的域上调用Console.WriteLine时，它将输出20。 下面推荐两本C#相关的书籍，以方便大家应对C#面试并学习好C#。 ● 《Professional C#》。这本书最大的特点是在附录中有几章专门写给已经有其他语言（如VB、C++和Java）经验的程序员，它详细讲述了C#和其他语言的区别，看了这几章之后就不会把C#和之前掌握的语言相混淆。 ● Jeffrey Richter的《CLR Via C#》。该书不仅深入地介绍了C#语言，同时对CLR及.NET做了全面的剖析。如果能够读懂这本书，那么我们就能深入理解装箱卸箱、垃圾回收、反射等概念，知其然的同时也能知其所以然，通过C#相关的面试自然也就不难了。 面试题2：实现Singleton模式 题目：设计一个类，我们只能生成该类的一个实例。 只能生成一个实例的类是实现了Singleton（单例）模式的类型。由于设计模式在面向对象程序设计中起着举足轻重的作用，在面试过程中很多公司都喜欢问一些与设计模式相关的问题。在常用的模式中，Singleton是唯一一个能够用短短几十行代码完整实现的模式。因此，写一个Singleton的类型是一个很常见的面试题。 不好的解法一：只适用于单线程环境 由于要求只能生成一个实例，因此我们必须把构造函数设为私有函数以禁止他人创建实例。我们可以定义一个静态的实例，在需要的时候创建该实例。下面定义类型Singleton1就是基于这个思路的实现：  上述代码在Singleton的静态属性Instance中，只有在instance为null的时候才创建一个实例以避免重复创建。同时我们把构造函数定义为私有函数，这样就能确保只创建一个实例。 不好的解法二：虽然在多线程环境中能工作但效率不高 解法一中的代码在单线程的时候工作正常，但在多线程的情况下就有问题了。设想如果两个线程同时运行到判断instance是否为null的if语句，并且instance的确没有创建时，那么两个线程都会创建一个实例，此时类型Singleton1就不再满足单例模式的要求了。为了保证在多线程环境下我们还是只能得到类型的一个实例，需要加上一个同步锁。把Singleton1稍做修改得到了如下代码：  我们还是假设有两个线程同时想创建一个实例。由于在一个时刻只有一个线程能得到同步锁，当第一个线程加上锁时，第二个线程只能等待。当第一个线程发现实例还没有创建时，它创建出一个实例。接着第一个线程释放同步锁，此时第二个线程可以加上同步锁，并运行接下来的代码。这个时候由于实例已经被第一个线程创建出来了，第二个线程就不会重复创建实例了，这样就保证了我们在多线程环境中也只能得到一个实例。 但是类型Singleton2还不是很完美。我们每次通过属性Instance得到Singleton2的实例，都会试图加上一个同步锁，而加锁是一个非常耗时的操作，在没有必要的时候我们应该尽量避免。 可行的解法：加同步锁前后两次判断实例是否已存在 我们只是在实例还没有创建之前需要加锁操作，以保证只有一个线程创建出实例。而当实例已经创建之后，我们已经不需要再做加锁操作了。于是我们可以把解法二中的代码再做进一步的改进：  Singleton3中只有当instance为null即没有创建时，需要加锁操作。当instance已经创建出来之后，则无须加锁。因为只在第一次的时候instance为null，因此只在第一次试图创建实例的时候需要加锁。这样Singleton3的时间效率比Singleton2要好很多。 Singleton3用加锁机制来确保在多线程环境下只创建一个实例，并且用两个if判断来提高效率。这样的代码实现起来比较复杂，容易出错，我们还有更加优秀的解法。 强烈推荐的解法一：利用静态构造函数 C#的语法中有一个函数能够确保只调用一次，那就是静态构造函数，我们可以利用C#这个特性实现单例模式如下：  Singleton4的实现代码非常简洁。我们在初始化静态变量instance的时候创建一个实例。由于C#是在调用静态构造函数时初始化静态变量，.NET运行时能够确保只调用一次静态构造函数，这样我们就能够保证只初始化一次instance。 C#中调用静态构造函数的时机不是由程序员掌控的，而是当.NET运行时发现第一次使用一个类型的时候自动调用该类型的静态构造函数。因此在Singleton4中，实例instance并不是第一次调用属性Singleton4.Instance的时候创建，而是在第一次用到Singleton4的时候就会被创建。假设我们在Singleton4中添加一个静态方法，调用该静态函数是不需要创建一个实例的，但如果按照Singleton4的方式实现单例模式，则仍然会过早地创建实例，从而降低内存的使用效率。 强烈推荐的解法二：实现按需创建实例 最后的一个实现Singleton5则很好地解决了Singleton4中的实例创建时机过早的问题：  在上述Singleton5的代码中，我们在内部定义了一个私有类型Nested。当第一次用到这个嵌套类型的时候，会调用静态构造函数创建Singleton5的实例instance。类型Nested只在属性Singleton5.Instance中被用到，由于其私有属性他人无法使用Nested类型。因此当我们第一次试图通过属性Singleton5.Instance得到Singleton5的实例时，会自动调用Nested的静态构造函数创建实例instance。如果我们不调用属性Singleton5.Instance，那么就不会触发.NET运行时调用Nested，也不会创建实例，这样就真正做到了按需创建。 解法比较 在前面的5种实现单例模式的方法中，第一种方法在多线程环境中不能正常工作，第二种模式虽然能在多线程环境中正常工作但时间效率很低，都不是面试官期待的解法。在第三种方法中我们通过两次判断一次加锁确保在多线程环境能高效率地工作。第四种方法利用C#的静态构造函数的特性，确保只创建一个实例。第五种方法利用私有嵌套类型的特性，做到只在真正需要的时候才会创建实例，提高空间使用效率。如果在面试中给出第四种或者第五种解法，毫无疑问会得到面试官的青睐。 源代码： 本题完整的源代码详见02\_Singleton项目。 本题考点： ● 考查对单例（Singleton）模式的理解。 ● 考查对C#的基础语法的理解，如静态构造函数等。 ● 考查对多线程编程的理解。 本题扩展： 在前面的代码中，5种单例模式的实现把类型标记为sealed，表示它们不能作为其他类型的基类。现在我们要求定义一个表示总统的类型President，可以从该类型继承出FrenchPresident和AmericanPresident等类型。这些派生类型都只能产生一个实例。请问该如何设计实现这些类型？ 2.3 数据结构 数据结构一直是技术面试的重点，大多数面试题都是围绕着数组、字符串、链表、树、栈及队列这几种常见的数据结构展开的，因此每一个应聘者都要熟练掌握这几种数据结构。 数组和字符串是两种最基本的数据结构，它们用连续内存分别存储数字和字符。链表和树是面试中出现频率最高的数据结构。由于操作链表和树需要操作大量的指针，应聘者在解决相关问题的时候一定要留意代码的鲁棒性，否则容易出现程序崩溃的问题。栈是一个与递归紧密相关的数据结构，同样队列也与广度优先遍历算法紧密相关。深刻理解这两种数据结构能帮助我们解决很多算法问题。 2.3.1 数组 数组可以说是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分利用。 由于数组中的内存是连续的，于是可以根据下标在O（1）时间读/写任何元素，因此它的时间效率是很高的。我们可以根据数组时间效率高的优点，用数组来实现简单的哈希表：把数组的下标设为哈希表的键值（Key），而把数组中的每一个数字设为哈希表的值（Value），这样每一个下标及数组中该下标对应的数字就组成了一个键值－值的配对。有了这样的哈希表，我们就可以在O（1）实现查找，从而可以快速高效地解决很多问题。面试题35“第一个只出现一次的字母”就是一个很好的例子。 为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，比如C++的STL中的vector。为了避免浪费，我们先为数组开辟较小的空间，然后往数组中添加数据。当数据的数目超过数组的容量时，我们再重新分配一块更大的空间（STL的vector每次扩充容量时，新的容量都是前一次的两倍），把之前的数据复制到新的数组中，再把之前的内存释放，这样就能减少内存的浪费。但我们也注意到每一次扩充数组容量时都有大量的额外操作，这对时间性能有负面影响，因此使用动态数组时要尽量减少改变数组容量大小的次数。 在C/C++中，数组和指针是相互关联又有区别的两个概念。当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。我们可以用一个指针来访问数组。但值得注意的是，C/C++没有记录数组的大小，因此用指针访问数组中的元素时，程序员要确保没有超出数组的边界。下面通过一个例子来了解数组和指针的区别。运行下面的代码，请问输出是什么？  答案是输出“20,4,4”。data1是一个数组，sizeof（data1）是求数组的大小。这个数组包含5个整数，每个整数占4字节，因此总共是20字节。data2声明为指针，尽管它指向了数组data1的第一个数字，但它的本质仍然是一个指针。在32位系统上，对任意指针求sizeof，得到的结果都是4。在C/C++中，当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。因此尽管函数GetSize的参数data被声明为数组，但它会退化为指针，size3的结果仍然是4。 面试题3：二维数组中的查找 题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。  在分析这个问题的时候，很多应聘者都会把二维数组画成矩形，然后从数组中选取一个数字，分3种情况来分析查找的过程。当数组中选取的数字刚好和要查找的数字相等时，就结束查找过程。如果选取的数字小于要查找的数字，那么根据数组排序的规则，要查找的数字应该在当前选取的位置的右边或者下边（如图2.1（a）所示）。同样，如果选取的数字大于要查找的数字，那么要查找的数字应该在当前选取的位置的上边或者左边（如图2.1（b）所示）。   图2.1 二维数组中的查找 注：在数组中间选择一个数（深色方格），根据它的大小判断要查找的数字可能出现的区域（阴影部分）。 在上面的分析中，由于要查找的数字相对于当前选取的位置有可能在两个区域中出现，而且这两个区域还有重叠，这问题看起来就复杂了，于是很多人就卡在这里束手无策了。 当我们需要解决一个复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，试图寻找普遍的规律。针对这个问题，我们不妨也从一个具体的例子入手。下面我们以在题目中给出的数组中查找数字7为例来一步步分析查找的过程。 前面我们之所以遇到难题，是因为我们在二维数组的中间选取一个数字来和要查找的数字做比较，这样导致下一次要查找的是两个相互重叠的区域。如果我们从数组的一个角上选取数字来和要查找的数字做比较，情况会不会变简单呢？ 首先我们选取数组右上角的数字9。由于9大于7，并且9还是第4列的第一个（也是最小的）数字，因此7不可能出现在数字9所在的列。于是我们把这一列从需要考虑的区域内剔除，之后只需要分析剩下的3列（如图2.2（a）所示）。在剩下的矩阵中，位于右上角的数字是8。同样8大于7，因此8所在的列我们也可以剔除。接下来我们只要分析剩下的两列即可（如图2.2（b）所示）。 在由剩余的两列组成的数组中，数字2位于数组的右上角。2小于7，那么要查找的7可能在2的右边，也有可能在2的下边。在前面的步骤中，我们已经发现2右边的列都已经被剔除了，也就是说7不可能出现在2的右边，因此7只有可能出现在2的下边。于是我们把数字2所在的行也剔除，只分析剩下的三行两列数字（如图2.2（c）所示）。在剩下的数字中，数字4位于右上角，和前面一样，我们把数字4所在的行也删除，最后剩下两行两列数字（如图2.2（d）所示）。     图2.2 在二维数组中查找7的步骤 注：矩阵中加阴影背景的区域是下一步查找的范围。 在剩下的两行两列4个数字中，位于右上角的刚好就是我们要查找的数字7，于是查找过程就可以结束了。 总结上述查找的过程，我们发现如下规律：首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。 把整个查找过程分析清楚之后，我们再写代码就不是一件很难的事情了。下面是上述思路对应的参考代码：  在前面的分析中，我们每一次都是选取数组查找范围内的右上角数字。同样，我们也可以选取左下角的数字。感兴趣的读者不妨自己分析一下每次都选取左下角的查找过程。但我们不能选择左上角或者右下角。以左上角为例，最初数字1位于初始数组的左上角，由于1小于7，那么7应该位于1的右边或者下边。此时我们既不能从查找范围内剔除1所在的行，也不能剔除1所在的列，这样我们就无法缩小查找的范围。 源代码： 本题完整的源代码详见03\_FindInPartiallySortedMatrix项目。 测试用例： ● 二维数组中包含查找的数字（查找的数字是数组中的最大值和最小值，查找的数字介于数组中的最大值和最小值之间）。 ● 二维数组中没有查找的数字（查找的数字大于数组中的最大值，查找的数字小于数组中的最小值，查找的数字在数组的最大值和最小值之间但数组中没有这个数字）。 ● 特殊输入测试（输入空指针）。 本题考点： ● 考查应聘者对二维数组的理解及编程能力。二维数组在内存中占据连续的空间。在内存中从上到下存储各行元素，在同一行中按照从左到右的顺序存储。因此我们可以根据行号和列号计算出相对于数组首地址的偏移量，从而找到对应的元素。 ● 考查应聘者分析问题的能力。当应聘者发现问题比较复杂时，能不能通过具体的例子找出其中的规律，是能否解决这个问题的关键所在。这个题目只要从一个具体的二维数组的右上角开始分析，就能找到查找的规律，从而找到解决问题的突破口。 2.3.2 字符串 字符串是由若干字符组成的序列。由于字符串在编程时使用的频率非常高，为了优化，很多语言都对字符串做了特殊的规定。下面分别讨论C/C++和C#中字符串的特性。 C/C++中每个字符串都以字符'\\0'作为结尾，这样我们就能很方便地找到字符串的最后尾部。但由于这个特点，每个字符串中都有一个额外字符的开销，稍不留神就会造成字符串的越界。比如下面的代码：  我们先声明一个长度为10的字符数组，然后把字符串"0123456789"复制到数组中。"0123456789"这个字符串看起来只有10个字符，但实际上它的末尾还有一个'\\0'字符，因此它的实际长度为11个字节。要正确地复制该字符串，至少需要一个长度为11个字节的数组。 为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，它们实际上会指向相同的内存地址。但用常量内存初始化数组，情况却有所不同。下面通过一个面试题来学习这一知识点。运行下面的代码，得到的结果是什么？  str1和str2是两个字符串数组，我们会为它们分配两个长度为12个字节的空间，并把"hello world"的内容分别复制到数组中去。这是两个初始地址不同的数组，因此str1和str2的值也不相同，所以输出的第一行是”str1 and str2 are not same”。 str3和str4是两个指针，我们无须为它们分配内存以存储字符串的内容，而只需要把它们指向"hello world”在内存中的地址就可以了。由于"hello world”是常量字符串，它在内存中只有一个拷贝，因此str3和str4指向的是同一个地址。所以比较str3和str4的值得到的结果是相同的，输出的第二行是”str3 and str4 are same”。 在C#中，封装字符串的类型System.String有一个非常特殊的性质：String中的内容是不能改变的。一旦试图改变String的内容，就会产生一个新的实例。请看下面的C#代码：  虽然我们对str做了ToUpper和Insert两个操作，但操作的结果都是生成一个新的String实例并在返回值中返回，str本身的内容都不会发生改变，因此最终str的值仍然是"hello"。由此可见，如果试图改变String的内容，改变之后的值只可以通过返回值得到。用String作连续多次修改，每一次修改都会产生一个临时对象，这样开销太大会影响效率。为此C#定义了一个新的与字符串相关的类型StringBuilder，它能容纳修改后的结果。因此如果要连续多次修改字符串内容，用StringBuilder是更好的选择。 和修改String内容类似，如果我们试图把一个常量字符串赋值给一个String实例，也不是把String的内容改成赋值的字符串，而是生成一个新的String实例。请看下面的代码：  在上面的代码中，我们先判断String是值类型还是引用类型。类型String的定义是public sealed class String {...}。既然是class，那么String自然就是引用类型。接下来在方法ModifyString里，对text赋值一个新的字符串。我们要记得text的内容是不能被修改的。此时会先生成一个新的内容是"world"的String实例，然后把text指向这个新的实例。由于参数text没有加ref或者out，出了方法ModifyString之后，text还是指向原来的字符串，因此输出仍然是"hello"。要想实现出了函数之后text变成"world"的效果，我们必须把参数text标记ref或者out。 面试题4：替换空格 题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。 在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如'#'的ASCII码为35，即十六进制的0x23，它在URL中被替换为"%23"。 看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成'%'、'2'和'0'这3个字符，因此字符串会变长。如果是在原来的字符串上做替换，那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换，那么我们可以自己分配足够多的内存。由于有两种不同的解决方案，我们应该向面试官问清楚，让他明确告诉我们他的需求。假设面试官让我们在原来的字符串上做替换，并且保证输入的字符串后面有足够多的空余内存。 时间复杂度为O（n2）的解法，不足以拿到Offer 现在我们考虑怎么做替换操作。最直观的做法是从头到尾扫描字符串，每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移两个字节，否则就有两个字符被覆盖了。 举个例子，我们从头到尾把"We are happy."中的每一个空格替换成"%20"。为了形象起见，我们可以用一个表格来表示字符串，表格中的每个格子表示一个字符（如图2.3（a）所示）。  图2.3 从前往后把字符串中的空格替换成'%20'的过程 注：（a）字符串"We are happy."。（b）把字符串中的第一个空格替换成'%20'。灰色背景表示需要移动的字符。（c）把字符串中的第二个空格替换成'%20'。浅灰色背景表示需要移动一次的字符，深灰色背景表示需要移动两次的字符。 我们替换第一个空格，这个字符串变成图2.3（b）中的内容，表格中灰色背景的格子表示需要做移动的区域。接着我们替换第二个空格，替换之后的内容如图2.3（c）所示。同时，我们注意到用深灰色背景标注的"happy"部分被移动了两次。 假设字符串的长度是n。对每个空格字符，需要移动后面O（n）个字符，因此对含有O（n）个空格字符的字符串而言总的时间效率是O（n2）。 当我们把这种思路阐述给面试官后，他不会就此满意，他将让我们寻找更快的方法。在前面的分析中，我们发现数组中很多字符都移动了很多次，能不能减少移动次数呢？答案是肯定的。我们换一种思路，把从前向后替换改成从后向前替换。 时间复杂度为O（n）的解法，搞定Offer就靠它了 我们可以先遍历一次字符串，这样就能统计出字符串中空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。我们还是以前面的字符串"We are happy."为例，"We are happy."这个字符串的长度是14（包括结尾符号'\\0'），里面有两个空格，因此替换之后字符串的长度是18。 我们从字符串的后面开始复制和替换。首先准备两个指针，P1和P2。P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾（如图2.4（a）所示）。接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。此时字符串包含如图2.4（b）所示，灰色背景的区域是做了字符拷贝（移动）的区域。碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把P2向前移动3格如图2.4（c）所示。 我们接着向前复制，直到碰到第二个空格（如图2.4（d）所示）。和上一次一样，我们再把P1向前移动1格，并把P2向前移动3格插入"%20"（如图2.4（e）所示）。此时P1和P2指向同一位置，表明所有空格都已经替换完毕。  图2.4 从后往前把字符串中的空格替换成“%20”的过程 注：图中带有阴影的区域表示被移动的字符。（a）把第一个指针指向字符串的末尾，把第二个指针指向替换之后的字符串的末尾。（b）依次复制字符串的内容，直至第一个指针碰到第一个空格。（c）把第一个空格替换成'%20'，把第一个指针向前移动1格，把第二个指针向前移动3格。（d）依次向前复制字符串中的字符，直至碰到空格。（e）替换字符串中的倒数第二个空格，把第一个指针向前移动1格，把第二个指针向前移动3格。 从上面的分析我们可以看出，所有的字符都只复制（移动）一次，因此这个算法的时间效率是O（n），比第一个思路要快。 在面试的过程中，我们也可以和前面的分析一样画一两个示意图解释自己的思路，这样既能帮助我们理清思路，也能使我们和面试官的交流变得更加高效。在面试官肯定我们的思路之后，就可以开始写代码了。下面是参考代码：  源代码： 本题完整的源代码详见04\_ReplaceBlank项目。 测试用例： ● 输入的字符串中包含空格（空格位于字符串的最前面，空格位于字符串的最后面，空格位于字符串的中间，字符串中有连续多个空格）。 ● 输入的字符串中没有空格。 ● 特殊输入测试（字符串是个NULL指针、字符串是个空字符串、字符串只有一个空格字符、字符串中只有连续多个空格）。 本题考点： ● 考查对字符串的编程能力。 ● 考查分析时间效率的能力。我们要能清晰地分析出两种不同方法的时间效率各是多少。 ● 考查对内存覆盖是否有高度的警惕。在分析得知字符串会变长之后，我们能够意识到潜在的问题，并主动和面试官沟通以寻找问题的解决方案。 ● 考查思维能力。在从前到后替换的思路被面试官否定之后，我们能迅速想到从后往前替换的方法，这是解决此题的关键。 相关题目： 有两个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，把A2中的所有数字插入到A1中并且所有的数字是排序的。 和前面的例题一样，很多人首先想到的办法是在A1中从头到尾复制数字，但这样就会出现多次复制一个数字的情况。更好的办法是从尾到头比较A1和A2中的数字，并把较大的数字复制到A1的合适位置。 举一反三： 合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。 2.3.3 链表 链表应该是面试时被提及最频繁的数据结构。链表的结构很简单，它由指针把若干个结点连接成链状结构。链表的创建、插入结点、删除结点等操作都只需要20行左右的代码就能实现，其代码量比较适合面试。而像哈希表、有向图等复杂数据结构，实现它们的一个操作需要的代码量都较大，很难在几十分钟的面试中完成。另外，由于链表是一种动态的数据结构，其操作需要对指针进行操作，因此应聘者需要有较好的编程功底才能写出完整的操作链表的代码。而且链表这种数据结构很灵活，面试官可以用链表来设计具有挑战性的面试题。基于上述几个原因，很多面试官都特别青睐链表相关的题目。 我们说链表是一种动态数据结构，是因为在创建链表时，无须知道链表的长度。当插入一个结点时，我们只需要为新结点分配内存，然后调整指针的指向来确保新结点被链接到链表当中。内存分配不是在创建链表时一次性完成，而是每添加一个结点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。如果单向链表的结点定义如下：  那么往该链表的末尾中添加一个结点的C语言代码如下：  在上面的代码中，我们要特别注意函数的第一个参数pHead是一个指向指针的指针。当我们往一个空链表中插入一个结点时，新插入的结点就是链表的头指针。由于此时会改动头指针，因此必须把pHead参数设为指向指针的指针，否则出了这个函数pHead仍然是一个空指针。 由于链表中的内存不是一次性分配的，因而我们无法保证链表的内存和数组一样是连续的。因此如果想在链表中找到它的第i个结点，我们只能从头结点开始，沿着指向下一个结点的指针遍历链表，它的时间效率为O（n）。而在数组中，我们可以根据下标在O（1）时间内找到第i个元素。下面是在链表中找到第一个含有某值的结点并删除该结点的代码：  除了简单的单向链表经常被设计为面试题之外（面试题5“从尾到头输出链表”、面试题13“在O（1）时间删除链表结点”、面试题15“链表中的倒数第k个结点”、面试题16“反转链表”、面试题17“合并两个排序的链表”、面试题37“两个链表的第一个公共结点”等），链表的其他形式同样也备受面试官的青睐。 ● 把链表的末尾结点的指针指向头结点，从而形成一个环形链表（面试题45“圆圈中最后剩下的数字”）。 ● 链表中的结点中除了有指向下一个结点的指针，还有指向前一个结点的指针。这就是双向链表（面试题27“二叉搜索树与双向链表”）。 ● 链表中的结点中除了有指向下一个结点的指针，还有指向任意结点的指针，这就是复杂链表（面试题26“复杂链表的复制”）。 面试题5：从尾到头打印链表 题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表结点定义如下：  看到这道题后，很多人的第一反应是从头到尾输出将会比较简单，于是我们很自然地想到把链表中链接结点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了。但该方法会改变原来链表的结构。是否允许在打印链表的时候修改链表的结构？这个取决于面试官的需求，因此在面试的时候我们要询问清楚面试官的要求。 面试小提示： 在面试中如果我们打算修改输入的数据，最好先问面试官是不是允许做修改。 通常打印是一个只读操作，我们不希望打印时修改内容。假设面试官也要求这个题目不能改变链表的结构。 接下来我们想到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”，我们可以用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。这种思路的实现代码如下：  既然想到了用栈来实现这个函数，而递归在本质上就是一个栈结构，于是很自然地又想到了用递归来实现。要实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。 基于这样的思路，不难写出如下代码：  上面的基于递归的代码看起来很简洁，但有个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显式用栈基于循环实现的代码的鲁棒性要好一些。更多关于循环和递归的讨论，详见本书的2.4.2节。 测试用例： ● 功能测试（输入的链表有多个结点，输入的链表只有一个结点）。 ● 特殊输入测试（输入的链表头结点指针为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。  图2.5 一个二叉树的例子 这3种遍历都有递归和循环两种不同的实现方法，每一种遍历的递归实现都比循环实现要简捷很多。很多面试官喜欢直接或间接考查遍历（面试题39“二叉树的深度”、面试题18“树的子结构”、面试题25“二叉树中和为某一值的路径”）的具体代码实现，面试题6“重建二叉树”、面试题24“二叉树的后序遍历序列”也是考查对遍历特点的理解，因此应聘者应该对这3种遍历的6种实现方法都了如指掌。 ● 宽度优先遍历：先访问树的第一层结点，再访问树的第二层结点……一直到访问到最下面一层结点。在同一层结点中，以从左到右的顺序依次访问。我们可以对包括二叉树在内的所有树进行宽度优先遍历。图2.5中的二叉树的宽度优先遍历的顺序是10、6、14、4、8、12、16。 面试题23“从上到下遍历二叉树”就是考查宽度优先遍历算法的题目。 二叉树有很多特例，二叉搜索树就是其中之一。在二叉搜索树中，左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。图2.5中的二叉树就是一棵二叉搜索树。我们可以平均在O（logn）的时间内根据数值在二叉搜索树中找到一个结点。二叉搜索树的面试题有很多，比如面试题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.6 根据前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}重建的二叉树 在二叉树的前序遍历序列中，第一个数字总是树的根结点的值。但在中序遍历序列中，根结点的值在序列的中间，左子树的结点的值位于根结点的值的左边，而右子树的结点的值位于根结点的值的右边。因此我们需要扫描中序遍历序列，才能找到根结点的值。 如图2.7所示，前序遍历序列的第一个数字1就是根结点的值。扫描中序遍历序列，就能确定根结点的值的位置。根据中序遍历特点，在根结点的值1前面的3个数字都是左子树结点的值，位于1后面的数字都是右子树结点的值。  图2.7 在二叉树的前序遍历和中序遍历的序列中确定根结点的值、左子树结点的值和右子树结点的值 由于在中序遍历序列中，有3个数字是左子树结点的值，因此左子树总共有3个左子结点。同样，在前序遍历的序列中，根结点后面的3个数字就是3个左子树结点的值，再后面的所有数字都是右子树结点的值。这样我们就在前序遍历和中序遍历两个序列中，分别找到了左右子树对应的子序列。 既然我们已经分别找到了左、右子树的前序遍历序列和中序遍历序列，我们可以用同样的方法分别去构建左右子树。也就是说，接下来的事情可以用递归的方法去完成。 在想清楚如何在前序遍历和中序遍历的序列中确定左、右子树的子序列之后，我们可以写出如下的递归代码：   在函数ConstructCore中，我们先根据前序遍历序列的第一个数字创建根结点，接下来在中序遍历序列中找到根结点的位置，这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后，我们就可以递归地调用函数ConstructCore，去分别构建它的左右子树。 源代码： 本题完整的源代码详见06\_ConstructBinaryTree项目。 测试用例： ● 普通二叉树（完全二叉树，不完全二叉树）。 ● 特殊二叉树（所有结点都没有右子结点的二叉树，所有结点都没有左子结点的二叉树，只有一个结点的二叉树）。 ● 特殊输入测试（二叉树的根结点指针为NULL、输入的前序遍历序列和中序遍历序列不匹配）。 本题考点： ● 考查应聘者对二叉树的前序遍历、中序遍历的理解程度。只有对二叉树的不同遍历算法有了深刻的理解，应聘者才有可能在遍历序列中划分出左、右子树对应的子序列。 ● 考查应聘者分析复杂问题的能力。我们把构建二叉树的大问题分解成构建左、右子树的两个小问题。我们发现小问题和大问题在本质上是一致的，因此可以用递归的方式解决。更多关于分解复杂问题的讨论，请参考本书的4.4节。 2.3.5 栈和队列 栈是一个非常常见的数据结构，它在计算机领域中被广泛应用，比如操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等。栈的特点是后进先出，即最后被压入（push）栈的元素会第一个被弹出（pop）。在面试题22“栈的压入、弹出序列”中，我们再详细分析进栈和出栈序列的特点。 通常栈是一个不考虑排序的数据结构，我们需要O（n）时间才能找到栈中最大或者最小的元素。如果想要在O（1）时间内得到栈的最大或者最小值，我们需要对栈做特殊的设计，详见面试题21“包含min函数的栈”。 队列是另外一种很重要的数据结构。和栈不同的是，队列的特点是先进先出，即第一个进入队列的元素将会第一个出来。在2.3.4节介绍的树的宽度优先遍历算法中，我们在遍历某一层树的结点时，把结点的子结点放到一个队列里，以备下一层结点的遍历。详细的代码参见面试题23“从上到下遍历二叉树”。 栈和队列虽然是特点针锋相对的两个数据结构，但有意思的是它们却相互联系。请看面试题7“用两个栈实现队列”，同时读者也可以考虑如何用两个队列实现栈。 面试题7：用两个栈实现队列 题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。  在上述队列的声明中可以看出，一个队列包含了两个栈stack1和stack2，因此这道题的意图是要求我们操作这两个“先进后出”的栈实现一个“先进先出”的队列CQueue。 我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素a，不妨先把它插入到stack1，此时stack1中的元素有{a}，stack2为空。再压入两个元素b和c，还是插入到stack1中，此时stack1中的元素有{a,b,c}，其中c位于栈顶，而stack2仍然是空的（如图2.8（a）所示）。 这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则，由于a比b、c先插入到队列中，最先被删除的元素应该是a。元素a存储在stack1中，但并不在栈顶上，因此不能直接进行删除。注意到stack2我们还一直没有使用过，现在是让stack2发挥作用的时候了。如果我们把stack1中的元素逐个弹出并压入stack2，元素在stack2中的顺序正好和原来在stack1中的顺序相反。因此经过3次弹出stack1和压入stack2操作之后，stack1为空，而stack2中的元素是{c,b,a}，这个时候就可以弹出stack2的栈顶a了。此时的stack1为空，而stack2的元素为{c,b}，其中b在栈顶（如图2.8（b）所示）。 如果我们还想继续删除队列的头部应该怎么办呢？剩下的两个元素是b和c，b比c早进入队列，因此b应该先删除。而此时b恰好又在栈顶上，因此直接弹出stack2的栈顶即可。这次弹出操作之后，stack1中仍然为空，而stack2为{c}（如图2.8（c）所示）。 从上面的分析中我们可以总结出删除一个元素的步骤：当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出。 接下来再插入一个元素d。我们还是把它压入stack1（如图2.8（d）所示），这样会不会有问题呢？我们考虑下一次删除队列的头部stack2不为空，直接弹出它的栈顶元素c（如图2.8（e）所示）。而c的确是比d先进入队列，应该在d之前从队列中删除，因此不会出现任何矛盾。  图2.8 用两个栈模拟一个队列的操作 总结完每一次在队列中插入和删除操作的过程之后，我们就可以开始动手写代码了。参考代码如下：  源代码： 本题完整的源代码详见07\_QueueWithTwoStacks项目。 测试用例： ● 往空的队列里添加、删除元素。 ● 往非空的队列里添加、删除元素。 ● 连续删除元素直至队列为空。 本题考点： ● 考查对栈和队列的理解。 ● 考查写与模板相关的代码的能力。 ● 考查分析复杂问题的能力。本题解法的代码虽然只有只有20几行代码，但形成正确的思路却不容易。应聘者能否通过具体的例子分析问题，通过画图的手段把抽象的问题形象化，从而解决这个相对比较复杂的问题，是能否顺利通过面试的关键。 相关题目： 用两个队列实现一个栈。 我们通过一系列栈的压入和弹出操作来分析用两个队列模拟一个栈的过程。如图2.9（a）所示，我们先往栈内压入一个元素a。由于两个队列现在都是空的，我们可以选择把a插入两个队列的任意一个。我们不妨把a插入queue1。接下来继续往栈内压入b、c两个元素，我们把它们都插入queue1。这个时候queue1包含3个元素a、b和c，其中a位于队列的头部，c位于队列的尾部。 现在我们考虑从栈内弹出一个元素。根据栈的后入先出原则，最后被压入栈的c应该最先被弹出。由于c位于queue1的尾部，而我们每次只能从队列的头部删除元素，因此我们可以先从queue1中依次删除元素a、b并插入到queue2中，再从queue1中删除元素c。这就相当于从栈中弹出元素c了（如图2.9（b）所示）。我们可以用同样的方法从栈内弹出元素b（如图2.9（c）所示） 接下来我们考虑往栈内压入一个元素d。此时queue1已经有一个元素，我们就把d插入到queue1的尾部（如图2.9（d）所示）。如果我们再从栈内弹出一个元素，此时被弹出的应该是最后被压入的d。由于d位于queue1的尾部，我们只能先从头删除queue1的元素并插入到queue2，直到在queue1中遇到d再直接把它删除（如图2.9（e）所示）。  图2.9 用两个队列模拟一个栈的操作 2.4 算法和数据操作 和数据结构一样，考查算法的面试题也备受面试官的青睐，其中排序和查找是面试时考查算法的重点。在准备面试的时候，我们应该重点掌握二分查找、归并排序和快速排序，做到能随时正确、完整地写出它们的代码。 有很多算法都可以用递归和循环两种不同的方式实现。通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。在面试的时候，我们可以根据题目的特点，甚至可以和面试官讨论选择合适的方法编程。 位运算可以看成是一类特殊的算法，它是把数字表示成二进制之后对0和1的操作。由于位运算的对象为二进制数字，所以不是很直观，但掌握它也不难，因为总共只有与、或、异或、左移和右移5种位运算。 2.4.1 查找和排序 查找和排序都是在程序设计中经常用到的算法。查找相对而言较为简单，不外乎顺序查找、二分查找、哈希表查找和二叉排序树查找。在面试的时候，不管是用循环还是用递归，面试官都期待应聘者能够信手拈来写出完整正确的二分查找代码，否则可能连继续面试的兴趣都没有。面试题8“旋转数组的最小数字”和面试题38“数字在排序数组中出现的次数”都可以用二分查找算法解决。 面试小提示： 如果面试题是要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，我们都可以尝试用二分查找算法。 哈希表和二叉排序树查找的重点在于考查对应的数据结构而不是算法。哈希表最主要的优点是我们利用它能够在O（1）时间查找某一元素，是效率最高的查找方式。但其缺点是需要额外的空间来实现哈希表。面试题35“第一个只出现一次的字符”就是用哈希表的特性来高效查找。与二叉排序树查找算法对应的数据结构是二叉搜索树，我们将在面试题24“二叉搜索树的后序遍历序列”和面试题27“二叉搜索树与双向链表”中详细介绍二叉搜索树的特点。 排序比查找要复杂一些。面试官会经常要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。强烈建议应聘者在准备面试的时候，一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。需要特别强调的是，很多公司的面试官喜欢在面试环节中要求应聘者写出快速排序的代码。应聘者不妨自己写一个快速排序的函数并用各种数据作测试。当测试都通过之后，再和经典的实现做比较，看看有什么区别。 实现快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边。这个函数可以如下实现：  函数RandomInRange用来生成一个在start和end之间的随机数，函数Swap的作用是用来交换两个数字。接下来我们可以用递归的思路分别对每次选中的数字的左右两边排序。下面就是递归实现快速排序的参考代码：  对一个长度为n的数组排序，只需把start设为0、把end设为n－1，调用函数QuickSort即可。 在前面的代码中，函数Partition除了可以用在快速排序算法中，还可以用来实现在长度为n的数组中查找第k大的数字。面试题29“数组中出现次数超过一半的数字”和面试题30“最小的k个数”都可以用这个函数来解决。 不同的排序算法适用的场合也不尽相同。快速排序虽然总体的平均效率是最好的，但也不是任何时候都是最优的算法。比如数组本身已经排好序了，而每一轮排序的时候都是以最后一个数字作为比较的标准，此时快速排序的效率只有O（n2）。因此在这种场合快速排序就不是最优的算法。在面试的时候，如果面试官要求实现一个排序算法，那么应聘者一定要问清楚这个排序应用的环境是什么、有哪些约束条件，在得到足够多的信息之后再选择最合适的排序算法。下面来看一个面试的片段： 面试官：请实现一个排序算法，要求时间效率O（n）。 应聘者：对什么数字进行排序，有多少个数字？ 面试官：我们想对公司所有员工的年龄排序。我们公司总共有几万名员工。 应聘者：也就是说数字的大小是在一个较小的范围之内的，对吧？ 面试官：嗯，是的。 应聘者：可以使用辅助空间吗？ 面试官：看你用多少辅助内存。只允许使用常量大小辅助空间，不得超过O（n）。 在面试的时候应聘者不要怕问面试官问题，只有多提问，应聘者才有可能明了面试官的意图。在上面的例子中，该应聘者通过几个问题就弄清楚了需排序的数字在一个较小的范围内，并且还可以用辅助内存。知道了这些限制条件，就不难写出如下的代码了：  公司员工的年龄有一个范围。在上面的代码中，允许的范围是0～99岁。数组timesOfAge用来统计每个年龄出现的次数。某个年龄出现了多少次，就在数组ages里设置几次该年龄，这样就相当于给数组ages排序了。该方法用长度100的整数数组作为辅助空间换来了O（n）的时间效率。 面试题8：旋转数组的最小数字 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 这道题最直观的解法并不难，从头到尾遍历数组一次，我们就能找出最小的元素。这种思路的时间复杂度显然是O（n）。但是这个思路没有利用输入的旋转数组的特性，肯定达不到面试官的要求。 我们注意到旋转之后的数组实际上可以划分为两个排序的子数组，而且前面的子数组的元素都大于或者等于后面子数组的元素。我们还注意到最小的元素刚好是这两个子数组的分界线。在排序的数组中我们可以用二分查找法实现O（logn）的查找。本题给出的数组在一定程度上是排序的，因此我们可以试着用二分查找法的思路来寻找这个最小的元素。 和二分查找法一样，我们用两个指针分别指向数组的第一个元素和最后一个元素。按照题目中旋转的规则，第一个元素应该是大于或者等于最后一个元素的（这其实不完全对，还有特例，后面再加以讨论）。 接着我们可以找到数组中间的元素。如果该中间元素位于前面的递增子数组，那么它应该大于或者等于第一个指针指向的元素。此时数组中最小的元素应该位于该中间元素的后面。我们可以把第一个指针指向该中间元素，这样可以缩小寻找的范围。移动之后的第一个指针仍然位于前面的递增子数组之中。 同样，如果中间元素位于后面的递增子数组，那么它应该小于或者等于第二个指针指向的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们可以把第二个指针指向该中间元素，这样也可以缩小寻找的范围。移动之后的第二个指针仍然位于后面的递增子数组之中。 不管是移动第一个指针还是第二个指针，查找范围都会缩小到原来的一半。接下来我们再用更新之后的两个指针，重复做新一轮的查找。 按照上述的思路，第一个指针总是指向前面递增数组的元素，而第二个指针总是指向后面递增数组的元素。最终第一个指针将指向前面子数组的最后一个元素，而第二个指针会指向后面子数组的第一个元素。也就是它们最终会指向两个相邻的元素，而第二个指针指向的刚好是最小的元素。这就是循环结束的条件。 以前面的数组{3,4,5,1,2}为例，我们先把第一个指针指向第0个元素，把第二个指针指向第4个元素（如图2.10（a）所示）。位于两个指针中间（在数组中的下标是2）的数字是5，它大于第一个指针指向的数字。因此中间数字5一定位于第一个递增子数组中，并且最小的数字一定位于它的后面。因此我们可以移动第一个指针让它指向数组的中间（图2.10（b）所示）。 此时位于这两个指针中间（在数组中的下标是3）的数字是1，它小于第二个指针指向的数字。因此这个中间数字1一定位于第二个递增字数组中，并且最小的数字一定位于它的前面或者它自己就是最小的数字。因此我们可以移动第二个指针指向两个指针中间的元素即下标为3的元素（如图2.10（c）所示）。  图2.10 在数组{3,4,5,1,2}中查找最小值的过程 注：旋转数组中包含两个递增排序的子数组，有阴影背景的是第二个子数组。（a）把P1指向数组的第一个数字，P2指向数组的最后一个数字。由于P1和P2中间的数字5大于P1指向的数字，中间的数字在第一个子数组中。下一步把P1指向中间的数字。（b）P1和P2中间的数字1小于P2指向的数字，中间的数字在第二个子数组中。下一步把P2指向中间的数字。（c）P1和P2指向两个相邻的数字，则P2指向的是数组中的最小数字。 此时两个指针的距离是1，表明第一个指针已经指向了第一个递增子数组的末尾，而第二个指针指向第二个递增子数组的开头。第二个子数组的第一个数字就是最小的数字，因此第二个指针指向的数字就是我们查找的结果。 基于这个思路，我们可以写出如下代码：  前面我们提到在旋转数组中，由于是把递增排序数组前面的若干个数字搬到数组的后面，因此第一个数字总是大于或者等于最后一个数字。但按照定义还有一个特例：如果把排序数组的前面的0个元素搬到最后面，即排序数组本身，这仍然是数组的一个旋转，我们的代码需要支持这种情况。此时，数组中的第一个数字就是最小的数字，可以直接返回。这就是在上面的代码中，把indexMid初始化为index1的原因。一旦发现数组中第一个数字小于最后一个数字，表明该数组是排序的，就可以直接返回第一个数字了。 上述代码是否就完美了呢？面试官会告诉我们其实不然。他将提示我们再仔细分析下标为index1和index2（index1和index2分别和图中P1和P2相对应）的两个数相同的情况。在前面的代码中，当这两个数相同，并且它们中间的数字（即indexMid指向的数字）也相同时，我们把indexMid赋值给了index1，也就是认为此时最小的数字位于中间数字的后面。是不是一定这样？ 我们再来看一个例子。数组{1,0,1,1,1}和数组{1,1,1,0,1}都可以看成是递增排序数组{0,1,1,1,1}的旋转，图2.11分别画出它们由最小数字分隔开的两个子数组。  图2.11 数组{0,1,1,1,1}的两个旋转{1,0,1,1,1}和{1,1,1,0,1} 注：在这两个数组中，第一个数字、最后一个数字和中间数字都是1，我们无法确定中间的数字1属于第一个递增子数组还是属于第二个递增子数组。第二个子数组用灰色背景表示。 在这两种情况中，第一个指针和第二个指针指向的数字都是1，并且两个指针中间的数字也是1，这3个数字相同。在第一种情况中，中间数字（下标为2）位于后面的子数组；在第二种情况中，中间数字（下标为2）位于前面的子数组中。因此，当两个指针指向的数字及它们中间的数字三者相同的时候，我们无法判断中间的数字是位于前面的子数组中还是后面的子数组中，也就无法移动两个指针来缩小查找的范围。此时，我们不得不采用顺序查找的方法。 在把问题分析清楚形成清晰的思路之后，我们就可以把前面的代码修改为：  源代码： 本题完整的源代码详见08\_MinNumberInRotatedArray项目。 测试用例： ● 功能测试（输入的数组是升序排序数组的一个旋转，数组中有重复数字或者没有重复数字）。 ● 边界值测试（输入的数组是一个升序排序的数组、只包含一个数字的数组）。 ● 特殊输入测试（输入NULL指针）。 本题考点： ● 考查对二分查找的理解。本题变换了二分查找的条件，输入的数组不是排序的，而是排序数组的一个旋转。这要求我们对二分查找的过程有深刻的理解。 ● 考查沟通学习能力。本题面试官提出了一个新的概念：数组的旋转。我们要在很短时间内学习理解这个新概念。在面试过程中如果面试官提出新的概念，我们可以主动和面试官沟通，多问几个问题把概念弄清楚。 ● 考查思维的全面性。排序数组本身是数组旋转的一个特例。另外，我们要考虑到数组中有相同数字的特例。如果不能很好地处理这些特例，就很难写出让面试官满意的完美代码。 2.4.2 递归和循环 如果我们需要重复地多次计算相同的问题，通常可以选择用递归或者循环两种不同的方法。递归是在一个函数的内部调用这个函数自身。而循环则是通过设置计算的初始值及终止条件，在一个范围内重复运算。比如求1＋2＋…＋n，我们可以用递归或者循环两种方式求出结果。对应的代码如下：  通常递归的代码会比较简洁。在上面的例子里，递归的代码只有一个语句，而循环则需要4个语句。在树的前序、中序、后序遍历算法的代码中，递归的实现明显要比循环简单得多。在面试的时候，如果面试官没有特别的要求，应聘者可以尽量多采用递归。 面试小提示： 通常基于递归实现的代码比基于循环实现的代码要简洁很多，更加容易实现。如果面试官没有特殊要求，应聘者可以优先采用递归的方法编程。 递归虽然有简洁的优点，但它同时也有显著的缺点。递归由于是函数调用自身，而函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。 另外，递归中有可能很多计算都是重复的，从而对性能带来很大的负面影响。递归的本质是把一个问题分解成两个或者多个小问题。如果多个小问题存在相互重叠的部分，那么就存在重复的计算。在面试题9“斐波那契数列”及面试题43“n个骰子的点数”中我们将详细地分析递归和循环的性能区别。 除了效率之外，递归还有可能引起更严重的问题：调用栈溢出。前面分析中提到需要为每一次函数调用在内存栈中分配空间，而每个进程的栈的容量是有限的。当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。在上述例子中，如果输入的参数比较小，如10，它们都能返回结果55。但如果输入的参数很大，如5000，那么递归代码在运行的时候就会出错，但运行循环的代码能得到正确的结果12502500。 面试题9：斐波那契数列 题目一：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列的定义如下：  效率很低的解法，挑剔的面试官不会喜欢 很多C语言教科书在讲述递归函数的时候，都会用Fibonacci作为例子，因此很多应聘者对这道题的递归解法都很熟悉。他们看到这道题的时候心中会忍不住一阵窃喜，因为他们能很快写出如下代码：  我们的教科书上反复用这个问题来讲解递归函数，并不能说明递归的解法最适合这道题目。面试官会提示我们上述递归的解法有很严重的效率问题并要求我们分析原因。 我们以求解f（10）为例来分析递归的求解过程。想求得f（10），需要先求得f（9）和f（8）。同样，想求得f（9），需要先求得f（8）和f（7）……我们可以用树形结构来表示这种依赖关系，如图2.12所示。  图2.12 基于递归求斐波那契数列的第10项的调用过程 我们不难发现在这棵树中有很多结点是重复的，而且重复的结点数会随着n的增大而急剧增加，这意味计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以n的指数的方式递增的。读者不妨求Fibonacci的第100项试试，感受一下这样递归会慢到什么程度。 面试官期待的实用解法 其实改进的方法并不复杂。上述递归代码之所以慢是因为重复的计算太多，我们只要想办法避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查找一下，如果前面已经计算过就不用再重复计算了。 更简单的办法是从下往上计算，首先根据f（0）和f（1）算出f（2），再根据f（1）和f（2）算出f（3）……依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O（n）。实现代码如下：  时间复杂度O（logn）但不够实用的解法 通常面试到这里也就差不多了，尽管我们还有比这更快的O（logn）算法。由于这种算法需要用到一个很生僻的数学公式，因此很少有面试官会要求我们掌握。不过以防不时之需，我们还是简要介绍一下这种算法。 在介绍这种方法之前，我们先介绍一个数学公式：  这个公式用数学归纳法不难证明，感兴趣的读者不妨自己证明一下。有了这个公式，我们只需要求得矩阵即可得到f（n）。现在的问题转为如何求矩阵的乘方。如果只是简单地从0开始循环，n次方需要n次运算，那其时间复杂度仍然是O（n），并不比前面的方法快。但我们可以考虑乘方的如下性质：  从上面的公式我们可以看出，我们想求得n次方，就要先求得n/2次方，再把n/2次方的结果平方一下即可。这可以用递归的思路实现。 由于很少有面试官要求编程实现这种思路，本书中不再列出完整的代码，感兴趣的读者请参考附带的源代码。不过这种基于递归用O（logn）的时间求得n次方的算法却值得我们重视。我们在面试题11“数值的整数次方”中再详细讨论这种算法。 解法比较 用不同的方法求解斐波那契数列的时间效率大不相同。第一种基于递归的解法虽然直观但时间效率很低，在实际软件开发中不会用这种方法，也不可能得到面试官的青睐。第二种方法把递归的算法用循环实现，极大地提高了时间效率。第三种方法把求斐波那契数列转换成求矩阵的乘方，是一种很有创意的算法。虽然我们可以用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）。分析到这里，我们不难看出这实际上就是斐波那契数列了。 源代码： 本题完整的源代码详见09\_Fibonacci项目。 测试用例： ● 功能测试（如输入3、5、10等）。 ● 边界值测试（如输入0、1、2）。 ● 性能测试（输入较大的数字，如40、50、100等）。 本题考点： ● 考查对递归、循环的理解及编码能力。 ● 考查对时间复杂度的分析能力。 ● 如果面试官采用的是青蛙跳台阶的问题，那同时还在考查应聘者的数学建模能力。 本题扩展： 在青蛙跳台阶的问题中，如果把条件改成：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？我们用数学归纳法可以证明f（n）=2n－1。 相关题目： 我们可以用2×1（图2.13的左边）的小矩形横着或者竖着去覆盖更大的矩形。请问用8个2×1的小矩形无重叠地覆盖一个2×8的大矩形（图2.13的右边），总共有多少种方法？  图2.13 一个2×1的矩形和2×8的矩形 我们先把2×8的覆盖方法记为f（8）。用第一个1×2小矩形去覆盖大矩形的最左边时有两个选择，竖着放或者横着放。当竖着放的时候，右边还剩下2×7的区域，这种情形下的覆盖方法记为f（7）。接下来考虑横着放的情况。当1×2的小矩形横着放在左上角的时候，左下角必须和横着放一个1×2的小矩形，而在右边还还剩下2×6的区域，这种情形下的覆盖方法记为f（6），因此f（8）=f（7）＋f（6）。此时我们可以看出，这仍然是斐波那契数列。 2.4.3 位运算 位运算是把数字用二进制表示之后，对每一位上0或者1的运算。二进制及其位运算是现代计算机学科的基石，很多底层的技术都离不开位运算，因此位运算相关的题目也经常出现在面试中。由于我们在日常生活中习惯了十进制，很多人看到二进制及位运算都觉得很难适应。 理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1。比如十进制的2转化为二进制之后是10，而十进制的10转换成二进制之后是1010。在程序员圈子里有一个流传了很久的笑话，说世界上有10种人，一种人知道二进制，而另一种人不知道二进制…… 除了二进制，我们还可以把数字表示成其他进制，比如表示时间分秒的六十进制等。针对不太熟悉的进制，已经出现了不少很有意思的面试题。比如： 在Excel 2003中，用A表示第1列，B表示第2列……Z表示第26列，AA表示第27列，AB表示第28列……以此类推。请写出一个函数，输入用字母表示的列号编码，输出它是第几列。 这是一道很新颖的关于进制的题目，其本质是把十进制数字用A～Z表示成二十六进制。如果想到这一点，解决这个问题就不难了。 其实二进制的位运算并不是很难掌握，因为位运算总共只有五种运算：与、或、异或、左移和右移。与、或和异或运算的规律我们可以用表2.1总结如下： 表2.1 与、或、异或的运算规律  左移运算符m<<n表示把m左移n位。左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。比如： 00001010<<2=00101000 10001010<<3=01010000 右移运算符m>>n表示把m右移n位。右移n位的时候，最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。下面是对两个8位有符号数作右移的例子： 00001010>>2=00000010 10001010>>3=11110001 面试题10“二进制中1的个数”就是直接考查位运算的例子，而面试题40“数组中只出现一次的数字”、面试题47“不用加减乘除做加法”等都是根据位运算的特点来解决问题。 面试题10：二进制中1的个数 题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。 可能引起死循环的解法 这是一道很基本的考查二进制和位运算的面试题。题目不是很难，面试官提出问题之后，我们很快就能形成一个基本的思路：先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位，此时原来处于从右边数起的第二位被移到最右边了，再判断是不是1。这样每次移动一位，直到整个整数变成0为止。现在的问题变成怎么判断一个整数的最右边是不是1了。这很简单，只要把整数和1做位与运算看结果是不是0就知道了。1除了最右边的一位之外所有位都是0。如果一个整数与1做与运算的结果是1，表示该整数最右边一位是1，否则是0。基于这个思路，我们很快就能写出如下代码：  面试官看了代码之后可能会问：把整数右移一位和把整数除以2在数学上是等价的，那上面的代码中可以把右移运算换成除以2吗？答案是否定的。因为除法的效率比移位运算要低得多，在实际编程中应尽可能地用移位运算符代替乘除法。 面试官接下来可能要问的第二个问题就是：上面的函数如果输入一个负数，比如0x80000000，运行的时候会发生什么情况？把负数0x80000000右移一位的时候，并不是简单地把最高位的1移到第二位变成0x40000000，而是0xC0000000。这是因为移位前是个负数，仍然要保证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成0xFFFFFFFF而陷入死循环。 常规解法 为了避免死循环，我们可以不右移输入的数字i。首先把i和1做与运算，判断i的最低位是不是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次低位是不是1……这样反复左移，每次都能判断i的其中一位是不是1。基于这种思路，我们可以把代码修改如下：  这个解法中循环的次数等于整数二进制的位数，32位的整数需要循环32次。下面再介绍一种算法，整数中有几个1就只需要循环几次。 能给面试官带来惊喜的解法 在分析这种算法之前，我们先来分析把一个数减去1的情况。如果一个整数不等于0，那么该整数的二进制表示中至少有一位是1。先假设这个数的最右边一位是1，那么减去1时，最后一位变成0而其他所有位都保持不变。也就是最后一位相当于做了取反操作，由1变成了0。 接下来假设最后一位不是1而是0的情况。如果该整数的二进制表示中最右边1位于第m位，那么减去1时，第m位由1变成0，而第m位之后的所有0都变成1，整数中第m位之前的所有位都保持不变。举个例子：一个二进制数1100，它的第二位是从最右边数起的一个1。减去1后，第二位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到的结果是1011。 在前面两种情况中，我们发现把一个整数减去1，都是把最右边的1变成0。如果它的右边还有0的话，所有的0都变成1，而它左边所有位都保持不变。接下来我们把一个整数和它减去1的结果做位与运算，相当于把它最右边的1变成0。还是以前面的1100为例，它减去1的结果是1011。我们再把1100和1011做位与运算，得到的结果是1000。我们把1100最右边的1变成了0，结果刚好就是1000。 我们把上面的分析总结起来就是：把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。基于这种思路，我们可以写出新的代码：  源代码： 本题完整的源代码详见10\_NumberOf1InBinary项目。 测试用例： ● 正数（包括边界值1、0x7FFFFFFF）。 ● 负数（包括边界值0x80000000、0xFFFFFFFF）。 ● 0。 本题考点： ● 考查对二进制及位运算的理解。 ● 考查分析、调试代码的能力。如果应聘者在面试过程中采用的是第一种思路，当面试官提示他输入负数将会出现问题时，面试官会期待他能在心中运行代码，自己找出运行出现死循环的原因。这要求应聘者有一定的调试功底。 相关题目： ● 用一条语句判断一个整数是不是2的整数次方。一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。根据前面的分析，把这个整数减去1之后再和它自己做与运算，这个整数中唯一的1就会变成0。 ● 输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制表示为1010，13的二进制表示为1101，需要改变1010中的3位才能得到1101。我们可以分为两步解决这个问题：第一步求这两个数的异或，第二步统计异或结果中1的位数。 举一反三： 把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。很多二进制的问题都可以用这个思路解决。 2.5 本章小结 本章着重介绍应聘者在面试之前应该认真准备的基础知识。为了应对编程面试，应聘者需要从编程语言、数据结构和算法3方面做好准备。 面试官通常采用概念题、代码分析题及编程题这3种常见题型来考查应聘者对某一编程语言的掌握程度。本章的2.2节讨论了C++/C#语言这3种题型的常见面试题。 数据结构题目一直是面试官考查的重点。数组和字符串是两种最基本的数据结构。链表应该是面试题中使用频率最高的一种数据结构。如果面试官想加大面试的难度，他很有可能会选用与树（尤其是二叉树）相关的面试题。由于栈与递归调用密切相关，队列在图（包括树）的宽度优先遍历中需要用到，因此应聘者也需要掌握这两种数据结构。 算法是面试官喜欢考查的另外一个重点。查找（特别是二分查找）和排序（特别是快速排序和归并排序）是面试中最经常考查的算法，应聘者一定要熟练掌握。另外，应聘者还要掌握分析时间复杂度的方法，理解即使是同一思路，基于循环和递归的不同实现它们的时间复杂度可能大不相同。 位运算是针对二进制数字的运算规律。只要应聘者熟练掌握了二进制的与、或、异或运算及左移、右移操作，就能解决与位运算相关的面试题。