【有书共读】《剑指Offer》第二章： 面试需要的基础知识
2.1 面试谈基础知识
基础知识反映了一个人的基本能力和基础素质，是以后工作中最核心的能力要求。一般考察：（1）数据结构和算法；（2）编程能力；（3）部分数学知识，如概率；（4）问题的分析和推理能力。
2.2 编程语言
C++
通常语言面试有3种类型。第一种题型是面试官直接询问应聘者对C++概念的理解；第二种是面试官拿出事先准备好的代码，让应聘者分析代码的运行结果；（3）要求应聘者写代码定义一个类型或者实现类型种的成员函数。
C#
面试官总是喜欢深究我们模棱两可的地方，因此我们要着重注意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: 旋转数组的最小数字
这个可以用二分法解决，但是在解法上要判断左右两边，哪一边是单调的，然后再根据这个来缩减区间。
2.4.3 回溯法
回溯法可以形象地用树状图来表示，
面试题12: 矩阵中的路径
简单的回溯法就可以搞定
面试题13:机器人的运动范围
回溯法，不过要加一个visit数组来标记。
2.4.4 动态规划与贪婪算法
面试题14:剪绳子
dp:f(n)=max(f(i)*f(n-i)),0<i<n;
贪婪算法：n>=5时，我们尽可能的剪长度为3的绳子；当剩下的长度为4时，把绳子剪成两段长度为2的绳子。
2.4.5 位运算
面试题15:二进制中1的个数
while(n){
count++;
n=(n-1)&n;
}
本章的笔记就到这里哈，如有疑问欢迎留言。
查看7道真题和解析
