剑指Offer
前言
- 面试题博客（http://zhedahht.blog.163.com/）
- 通常面试官除了期待应聘者写出的代码能够完成基本的功能之外，还能应对特殊情况并对非法输入进行合理的处理。
- 除此之外，有些面试官还喜欢考查应聘者的知识迁移能力、抽象建模能力和发散思维能力。
- 如果面试的时候遇到的题目很难，我们可以试图把一个大的复杂的问题分解成若干个小的简单的子问题，然后递归地去解决这些子问题。
- 如何从基本功能测试、边界值测试、性能测试等方面去设计测试用例，从而提高编写高质量代码的能力
推荐序一
- 应聘者要想做好面试，确实应把面试当作一门技巧来学习，更重要的是要提高自身的能力。
- 我希望读这本书的朋友不要只学一些技巧来对付面试，而是通过学习如何解决面试中的难题来提高自己的编程和解决问题的能力，进而提高自信心，在职场中能迅速成长。
第1章 面试的流程
- 对于初级程序员，我一般会偏向考查算法和数据结构，看应聘者的基本功；对于高级程序员，我会多关注专业技能和项目经验。”
- 应聘者在面试过程首先需要放松，不要过于紧张，这有助于后面解决问题时开拓思路。其次不要急于编写代码，应该先了解清楚所要解决的问题。
1.2 面试的三种形式
- 面试官让应聘者共享自己的桌面，远程观察应聘者编写及调试代码的过程
1.2.1 电话面试
- 应聘者在电话面试的时候应尽可能用形象化的语言把细节说清楚。
- 如果应聘者在面试的时候没有听清楚或者听懂面试官的问题，千万不要不懂装懂、答非所问，这是面试的大忌。当不确定面试官的问题的时候，应聘者一定要大胆地向面试官多提问，直到弄清楚面试官的意图为止。
- 大部分公司都会注重考查查找、排序等算法。应聘者可以在了解各种查找和排序算法的基础上，重点掌握二分查找、归并排序和快速排序
1.2.2 共享桌面远程面试
- 最后推荐问的问题是与招聘的职位或者项目相关的问题。
- 如果应聘者是先写单元测试用例，再写解决问题的函数，我相信面试官定会对你刮目相看，因为能做到测试在前、开发在后的程序员实在是太稀缺了，他会毫不犹豫地抛出绿色的橄榄枝。
1.2.3 现场面试
- 准备几个问题。每一轮面试的最后，面试官都会让应聘者问几个问题，应聘者可以提前准备好问题。
1.3 面试的三个环节
- 的过往经验；然后是技术面试，这一环节很有可能会要求应聘者现场写代码；最后一个环节是应聘者问几个自己最感兴趣的问题。下面将详细
- 在 C++中，有哪 4 个与类型转换相关的关键字？这些关键字各有什么特点，应该在什么场合下使用？
1.3.1 行为面试环节
- 通常如果应聘者在简历中说自己精通某一项技术，面试官就会对他有很高的期望值，因此会挑一些比较难的问题来问。这也是越装高手就越容易露馅的原因。
- 现在的工作做了一段时间，已经没有太多的激情了，因此希望寻找一份更有挑战的工作。然后具体论述为什么有些厌倦现在的职位，以及面试的职位我为什么会有兴趣。
1.3.2 技术面试环节
- 如果题目很简单，面试官就会期待应聘者能够很完整地解决问题，除了完成基本功能之外，还要考虑到边界条件、错误处理等各个方面。
- 面试官除了希望应聘者的代码能够完成基本的功能之外，还会关注应聘者是否考虑了边界条件、特殊输入（比如 NULL 指针，空字符串等）及错误处理。
- 如果在面试的时候遇到难题，我们有 3 种办法分析、解决复杂的问题：画图能使抽象问题形象化，举例使抽象问题具体化，分解使复杂问题简单化。
- 面试官的第一种方法是询问应聘者最近在看什么书、从中学到了哪些新技术。
- 知识迁移能力是一种特殊的学习能力
- 还有不少面试官喜欢考查应聘者的抽象建模能力和发散思维能力。
1.3.3 应聘者提问环节
- 在结束面试前的 5～10 分钟，面试官会给应聘者机会问几个问题，应聘者的问题的质量对面试的结果也有一定的影响。
1.4 本章小结
- 基础知识是否扎实、能否写出高质量的代码、思路是否清晰、是否有优化效率的能力，以及包括学习能力、沟通能力在内的综合素质是否优秀。
第2章 面试需要的基础知识
- C++中对内存的使用管理
- （1）数据结构和算法；（2）编程能力；（3）部分数学知识，如概率；（4）问题的分析和推理能力。”
- （1）编程基本功（特别喜欢字符串处理这一类的问题）；（2）并发控制；（3）算法、复杂度；（4）语言的基本概念。”
- 我会考查编程基础、计算机系统基础知识、算法以及设计能力。
- 对OS的理解程度。这些知识对于工作中常遇到的内存管理、文件操作、程序性能、多线程、程序安全等有重要帮助。对于OS理解比较深入的人对于偏底层的工作上手一般比较快。
2.2.1 C++
- 调用构造函数和析构函数只需要知道函数的地址即可，而这些函数的地址只与类型相关，而与类型的实例无关，编译器也不会因为这两个函数而在实例内添加任何额外的信息。
- 由于是传值参数，我们把形参复制到实参会调用复制构造函数。因此如果允许复制构造函数传值，就会在复制构造函数内调用复制构造函数，就会形成永无休止的递归调用从而导致栈溢出。因此 C++的标准不允许复制构造函数传值参数，在Visual Studio和GCC中，都将编译出错。要解决这个问题，我们可以把构造函数修改为A（const A&other），也就是把传值参数改成常量引用。
面试题1：赋值运算符函数
- 是否把返回值的类型声明为该类型的引用，并在函数结束前返回实例自身的引用（即*this）。只有返回一个引用，才可以允许连续赋值。否则如果函数的返回值是void，应用该赋值运算符将不能做连续赋值
- 这样只在分配内容成功之后再释放原来的内容，也就是当分配内存失败时我们能确保 CMyString 的实例不会被修改。我们还有一个更好的办法是先创建一个临时实例，再交换临时实例和原来的实例。
2.2.2 C#
- 如果没有标明成员函数或者成员变量的访问权限级别，在struct中默认的是public，而在class中默认的是private。
- 静态构造函数先初始化类型的静态变量，再执行函数体内的语句。
面试题2：实现Singleton模式
- Singleton的静态属性Instance中，只有在instance为null的时候才创建一个实例以避免重复创建。同时我们把构造函数定义为私有函数
2.3 数据结构
- 数组、字符串、链表、树、栈及队列这几种常见的数据结构展开的
2.3.1 数组
- 把数组的下标设为哈希表的键值（Key），而把数组中的每一个数字设为哈希表的值（Value），这样每一个下标及数组中该下标对应的数字就组成了一个键值-值的配对
- STL 的 vector 每次扩充容量时，新的容量都是前一次的两倍
- 当我们声明一个数组时，其数组的名字也是一个指针，该指针指向数组的第一个元素。
- 在C/C++中，当数组作为函数的参数进行传递时，数组就自动退化为同类型的指针。
面试题3：二维数组中的查找
- 当我们需要解决一个复杂的问题时，一个很有效的办法就是从一个具体的问题入手，通过分析简单具体的例子，试图寻找普遍的规律。
- 首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。
- 以左上角为例，最初数字1位于初始数组的左上角，由于1小于7，那么7应该位于1 的右边或者下边。此时我们既不能从查找范围内剔除1 所在的行，也不能剔除1所在的列，这样我们就无法缩小查找的范围。
- 特殊输入测试（输入空指针）
- 根据行号和列号计算出相对于数组首地址的偏移量
2.3.2 字符串
- C/C++ 中每个字符串都以字符'\0'作为结尾
- 为了节省内存，C/C++把常量字符串放到单独的一个内存区域。当几个指针赋值给相同的常量字符串时，它们实际上会指向相同的内存地址。但用常量内存初始化数组，情况却有所不同。
面试题4：替换空格
- 在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如'#'的ASCII码为35，即十六进制的0x23，它在URL中被替换为"%23"。
- 更好的办法是从尾到头比较A1和A2中的数字，并把较大的数字复制到A1的合适位置。
- 合并两个数组（包括字符串）时，如果从前往后复制每个数字（或字符）需要重复移动数字（或字符）多次，那么我们可以考虑从后往前复制，这样就能减少移动的次数，从而提高效率。
2.3.3 链表
- 由于此时会改动头指针，因此必须把 pHead 参数设为指向指针的指针，否则出了这个函数pHead仍然是一个空指针。
面试题5：从尾到头打印链表
- 面试题5：从尾到头打印链表
- 在面试中如果我们打算修改输入的数据，最好先问面试官是不是允许做修改。
- 递归在本质上就是一个栈结构，于是很自然地又想到了用递归来实现
- 当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显式用栈基于循环实现的代码的鲁棒性要好一些。
2.3.4 树
- 除了根结点之外每个结点只有一个父结点，根结点没有父结点；除了叶结点之外所有结点都有一个或多个子结点，叶结点没有子结点。父结点和子结点之间用指针链接。
- 这3种遍历都有递归和循环两种不同的实现方法，每一种遍历的递归实现都比循环实现要简捷很多。
- 在二叉搜索树中，左子结点总是小于或等于根结点，而右子结点总是大于或等于根结点。
面试题6：重建二叉树
- 在函数ConstructCore中，我们先根据前序遍历序列的第一个数字创建根结点，接下来在中序遍历序列中找到根结点的位置，这样就能确定左、右子树结点的数量
- 把构建二叉树的大问题分解成构建左、右子树的两个小问题。我们发现小问题和大问题在本质上是一致的，因此可以用递归的方式解决。
2.3.5 栈和队列
- 操作系统会给每个线程创建一个栈用来存储函数调用时各个函数的参数、返回地址及临时变量等
面试题7：用两个栈实现队列
- 面试题7：用两个栈实现队列
- 当 stack2 中不为空时，在 stack2 中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出。
- 当 stack2 中不为空时，在 stack2 中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，我们把stack1中的元素逐个弹出并压入stack2。由于先进入队列的元素被压到stack1的底端，经过弹出和压入之后就处于stack2的顶端了，又可以直接弹出。
2.4 算法和数据操作
- 在准备面试的时候，我们应该重点掌握二分查找、归并排序和快速排序，做到能随时正确、完整地写出它们的代码。
- 通常基于递归的实现方法代码会比较简洁，但性能不如基于循环的实现方法。
2.4.1 查找和排序
- 顺序查找、二分查找、哈希表查找和二叉排序树查找
- 如果面试题是要求在排序的数组（或者部分排序的数组）中查找一个数字或者统计某个数字出现的次数，我们都可以尝试用二分查找算法。
- 面试官会经常要求应聘者比较插入排序、冒泡排序、归并排序、快速排序等不同算法的优劣。强烈建议应聘者在准备面试的时候，一定要对各种排序算法的特点烂熟于胸，能够从额外空间消耗、平均时间复杂度和最差时间复杂度等方面去比较它们的优缺点。
- 快速排序算法的关键在于先在数组中选择一个数字，接下来把数组中的数字分为两部分，比选择的数字小的数字移到数组的左边，比选择的数字大的数字移到数组的右边
- 快速排序虽然总体的平均效率是最好的，但也不是任何时候都是最优的算法。比如数组本身已经排好序了，而每一轮排序的时候都是以最后一个数字作为比较的标准，此时快速排序的效率只有O（n2）
面试题8：旋转数组的最小数字
- 考查对二分查找的理解。本题变换了二分查找的条件，输入的数组不是排序的，而是排序数组的一个旋转。这要求我们对二分查找的过程有深刻的理解。
2.4.2 递归和循环
- 在面试的时候，如果面试官没有特别的要求，应聘者可以尽量多采用递归。
- 通常基于递归实现的代码比基于循环实现的代码要简洁很多，更加容易实现。如果面试官没有特殊要求，应聘者可以优先采用递归的方法编程。
- 函数调用是有时间和空间的消耗的：每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。
- 除了效率之外，递归还有可能引起更严重的问题：调用栈溢出。
面试题9：斐波那契数列
- 题目二：一只青蛙一次可以跳上1 级台阶，也可以跳上2 级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
- 在青蛙跳台阶的问题中，如果把条件改成：一只青蛙一次可以跳上 1级台阶，也可以跳上 2 级……它也可以跳上 n 级，此时该青蛙跳上一个 n级的台阶总共有多少种跳法？我们用数学归纳法可以证明f（n）=2n-1。
- 接下来考虑横着放的情况。当1×2的小矩形横着放在左上角的时候，左下角必须和横着放一个1×2的小矩形，而在右边还还剩下2×6的区域，这种情形下的覆盖方法记为f（6），因此f（8）=f（7）+f（6）。
2.4.3 位运算
- 但右移时处理最左边位的情形要稍微复杂一点。如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后在最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。
面试题10：二进制中1的个数
- 因为除法的效率比移位运算要低得多，在实际编程中应尽可能地用移位运算符代替乘除法。
- 把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。
- 把一个整数减去 1 之后再和原来的整数做位与运算，得到的结果相当于是把整数的二进制表示中的最右边一个1变成0。很多二进制的问题都可以用这个思路解决。
2.5 本章小结
- 查找（特别是二分查找）和排序（特别是快速排序和归并排序）是面试中最经常考查的算法，应聘者一定要熟练掌握。
第3章 高质量的代码
- 最不能容忍功能错误，忽略边界情况
3.3 代码的完整性
- 通常我们可以从功能测试、边界测试和负面测试三方面设计测试用例，以确保代码的完整性（如图3.2所示）。
- 第一种方式是函数用返回值来告知调用者是否出错。
- 第二种方式是当发生错误时设置一个全局变量。
- 第三种方式是异常。当函数运行出错的时候，我们就抛出一个异常，我们还可以根据不同的出错原因定义不同的异常类型。
面试题11：数值的整数次方
- 最后需要指出的是，由于0 的0 次方在数学上是没有意义的，因此无论是输出0 还是1 都是可以接受
- 由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接用等号（==）判断两个小数是否相等。如果两个小数的差的绝对值很小，比如小于0.0000001，就可以认为它们相等。
- 我们用右移运算符代替了除以2，用位与运算符代替了求余运算符（%）来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。
面试题12：打印1到最大的n位数
- 面试题12：打印1到最大的n位数
- 最常用也是最容易的方法是用字符串或者数组表达大数
- 如果面试题是关于 n位的整数并且没有限定 n的取值范围，或者是输入任意大小的整数，那么这个题目很有可能是需要考虑大数问题的。字符串是一个简单、有效的表示大数的方法。
面试题14：调整数组顺序使奇数位于偶数前面
- 面试题14：调整数组顺序使奇数位于偶数前面
3.4 代码的鲁棒性
- 也就是说解耦的好处就是提高了代码的重用性，为功能扩展提供了便利。
- 所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不合要求的输入予以合理的处理。
面试题15：链表中倒数第k个结点
- 第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；从第 k 步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
- 当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表。可以让其中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若干步。
面试题18：树的子结构
- 第一步在树A中找到和B的根结点的值一样的结点R，第二步再判断树A中以R为根结点的子树是不是包含和树B一样的结构。
第4章 解决面试题的思路
- “编码前讲自己的思路是一个考查指标。一个合格的应聘者应该在他做事之前明白自己要做的事情究竟是什么，以及该怎么做。一开始就编码的人员，除非后面表现非常优秀，否则很容易通不过。”
4.2 画图让抽象问题形象化
- 很多面试题很抽象，不是很容易找到解决办法。这时不妨画出一些与题目相关的图形，借以辅助自己观察和思考。图形能使抽象的问题具体化、形象化
- 求树的镜像的过程其实就是在遍历树的同时交换非叶结点的左右子结点
面试题19：二叉树的镜像
- 我们先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后，就得到了树的镜像。
面试题22：栈的压入、弹出序列
- 面试题22：栈的压入、弹出序列
- 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出。如果下一个弹出的数字不在栈顶，我们把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入栈顶为止。如果所有的数字都压入栈了仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。
面试题23：从上往下打印二叉树
- 每一次打印一个结点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都被打印出来为止。
- 不管是广度优先遍历一个有向图还是一棵树，都要用到队列。第一步我们把起始结点（对树而言是根结点）放入队列中。接下来每一次从队列的头部取出一个结点，遍历这个结点之后把从它能到达的结点（对树而言是子结点）都依次放入队列。我们重复这个遍历过程，直到队列中的结点全部被遍历为止。
面试题24：二叉搜索树的后序遍历序列
- 面试题24：二叉搜索树的后序遍历序列
- 如果面试题是要求处理一棵二叉树的遍历序列，我们可以先找到二叉树的根结点，再基于根结点把整棵树的遍历序列拆分成左子树对应的子序列和右子树对应的子序列，接下来再递归地处理这两个子序列。
- 面试题25：二叉树中和为某一值的路径
- 这里没有直接用STL中的stack的原因是在stack中只能得到栈顶元素，而我们打印路径的时候需要得到路径上的所有结点，因此在代码实现的时候std::stack不是最好的选择。
4.4 分解让复杂问题简单化
- 通常分治法思路都可以用递归的代码实现。
面试题26：复杂链表的复制
- 接下来我们再换一种思路，在不用辅助空间的情况下实现 O（n）的时间效率。第三种方法的第一步仍然是根据原始链表的每个结点 N创建对应的N’。这一次，我们把 N’链接在 N的后面。图4.8的链表经过这一步之后的结构，如图4.9所示。
面试题27：二叉搜索树与双向链表
- 面试题27：二叉搜索树与双向链表
5.2 时间效率
- 比如 C/C++程序员要养成采用引用（或指针）传递复杂类型参数的习惯。如果采用值传递的方式，从形参到实参会产生一次复制操作。这样的复制是多余的操作，我们应该尽量避免
面试题29：数组中出现次数超过一半的数字
- 一个是数组中的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为 1 时对应的数字。
面试题30：最小的k个数
- 如果基于数组的第 k 个数字来调整，使得比第k 个数字小的所有数字都位于数组的左边，比第k 个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。
面试题35：第一个只出现一次的字符
- 哈希表是一种比较复杂的数据结构，并且 C++的标准模板库中没有实现哈希表。
- 如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在某个字符串中出现的次数，我们可以考虑基于数组创建一个简单的哈希表。这样可以用很小的空间消耗换来时间效率的提升。
面试题37：两个链表的第一个公共结点
- 首先遍历两个链表得到它们的长度，就能知道哪个链表比较长，以及长的链表比短的链表多几个结点。在第二次遍历的时候，在较长的链表上先走若干步，接着再同时在两个链表上遍历，找到的第一个相同的结点就是它们的第一个公共结点。
5.4 本章小结
- 降低时间复杂度的第一个方法是改用更加高效的算法。
- 降低时间复杂度的第二个方法是用空间换取时间。
6.2 沟通能力和学习能力
- 第一种方法是询问应聘者最近在看什么书或者在做什么项目、从中学到了哪些新技术。
- 第二种方法是抛出一个新概念，接下来观察应聘者能不能在较短时间内理解这个新概念并解决相关的问题。
- 因此建议应聘者在面试过程中遇到不明白的地方多提问，这样面试官就会觉得你态度积极、求知欲望强烈，会给面试结果加分。
- 有些面试官故意一开始不把题目描述清楚，让题目存在一定的二义性。他期待应聘者能够一步步通过提问来弄明白题目的要求。
面试题39：二叉树的深度
- 由于这两个数字肯定不一样，那么异或的结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为 1 的位的位置，记为第 n 位。现在我们以第 n位是不是 1 为标准把原数组中的数字分成两个子数组，
6.4 抽象建模能力
- 建模的第一步是选择合理的数据结构来表述问题
- 建模的第二步是分析模型中的内在规律，并用编程语言表述这种规律。
第7章 两个面试案例
- 在介绍自己的项目经历时，应聘者可以参照S TA R模型，着重介绍自己完成的工作（包括基于什么平台、用了哪些技术、实现了哪些算法等），以及最终对项目组的贡献。
7.1 案例一：（面试题49）把字符串转换成整数
- 在 C++中，成员变量的初始化顺序只与它们在类中声明的顺序有关，而与在初始化列表中的顺序无关。