【有书共读】《剑指Offer》第二章：面试需要的基础知识

2.1 面试谈基础知识

基础知识反映了一个人的基本能力和基础素质，是以后工作中最核心的能力要求。一般考察：（1）数据结构和算法；（2）编程能力；（3）部分数学知识，如概率；（4）问题的分析和推理能力。

2.2 编程语言

C++

通常语言面试有3种类型。第一种题型是面试官直接询问应聘者对C++概念的理解；第二种是面试官拿出事先准备好的代码，让应聘者分析代码的运行结果；（3）要求应聘者写代码定义一个类型或者实现类型种的成员函数。

面试官总是喜欢深究我们模棱两可的地方，因此我们要着重注意C#和C++不同的语法特点。

除了关注C#和C++不同的知识点，还要格外关注C#一些特有的功能，比如反射，应用程序域等。

面试：实现singleton 模式

推荐解法：加同步锁前后两次判断实例是否已存在，利用静态构造函数，实现按需创建实例。

2.3 数据结构

2.3.1 数组

数组的内存分配是连续的，可以在O(1)的时间内读写任意元素，为了解决数组空间效率不高的问题，有设计了vector

面试题3: 数组中重复的数字。

先排序，再判断，时间复杂度为O(nlogn)，

用hash表为O(n)，空间复杂度O(n)

最好的方式是重排数组。如果在当前下表下有两个值，则有重复，空间为O(1),时间为O(n)

如果不能改变数组，则需要用二分法，时间复杂度为O(nlogn)

面试题4:二维数组中的查找

从右上开始，找到左下方就行了。

2.3.2 字符串

面试题5:替换空格

最优的解法是从后往前，先算出字符串的长度，然后从后面开始一个一个的移动到目标位置，把空格换成相应的字符串。

2.3.3 链表

面试题6:从尾到头打印链表

用栈，进而很自然的想到了用递归来实现

2.3.4 树

面试题7:重建二叉树

前序和中序能够构建二叉树，前序能够确定根结点，中序能够确定左右分支；同理，中序和后序也能够构建二叉树。

面试题8:二叉树的下一个节点

如果一个节点有右节点，那么它的下一个节点就是它的右子树中最左子节点。如果没有右子树，如果节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。如果一个节点没有右子树且是它父节点的右子节点，我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果存在，即为下一个节点。

2.3.5 栈和队列

面试题9:两个栈实现一个队列

有两个栈s1，s2，插入时，把值压入s1

删除一个元素时，如果s2不为空，则直接s2出栈，如果为空，则把s1的值压入s2中，然后s2出栈。

2.4 算法和数据操作

掌握排序算法的递归和非递归形式，根据面试题的性质尝试回溯法，dp法，还有位运算法。

2.4.1 递归和循环

如无特殊要求，递归比较简洁，多采用递归。

面试题10: 佩波那契数列

循环实现比递归实现更好

2.4.2 查找和排序

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