剑指Offer总结

经过2个多月的零零散散的刷题，终于搞定了剑指Offer中的67道面试题，这期间又经历了一场GE的数据分析岗简单面试，立刻体会到剑指offer的强大，除了里面的经典面试题之外，书中包含的软条件，面试套路，分析、回答问题的技巧也确确实实得好用。在刷完题之际，做一个简单的总结。这是我剑指offer的Java代码，供大家参考。

面试相关

1. 理解题目含义
   首先理解题目的含义，题目有没有什么坑，没听明白的可以再问问面试官。
   善于学习，沟通，提问，体现出主动积极的态度。如果能够针对面试题主动提出几个高质量的问题，面试官就会觉得他有很强的沟通能力和学习能力。
   有些面试官故意一开始不把题目描述清楚，让题目存在一定的二义性。他期待应聘者能够一步步通过提问来弄明白题目的要求。
   知识迁移能力先问一个简单的问题，完成简单问题之后，问一个相关的同时难度也更大的问题。

2. 想清楚后再开始写代码
   写代码之前先将思路，明白自己要做什么东西；可以通过举例子、画图等多种方式，解释清楚问题本身和问题解决方案。

3. 良好的代码命名和缩进对齐习惯

4. 能够单元测试

技术面试环节

自我介绍完，就开始了。

1. 扎实的基础知识
2. 高质量的代码
3. 清晰的思路
4. 优化效率的能力
5. 优秀的综合能力

现场面试要注意的地方

1. 时间、衣服得体，干净
2. 注意面试邀请函里的面试流程
   有可能会等很长时间，所以可以带一点提升醒脑的饮品
3. 准备几个问题，面试完之后，面试官会让面试者问几个问题
   先考虑面试官是做什么的，问的东西要他能知道的，答的上来的，也不要问和自己的职业没关系的问题，不要问薪水，不要打听面试结果。
   推荐的问题： 与招聘的职位或者项目相关的问题。
   可以事先在网上收集一些相关的信息，留意面试官说过的话。公司的主要业务、职位要求、与应聘岗位相关的项目、招聘相关的项目，可以从这里面找一两个点，然后向面试官提问。

做题相关

题目

斐波那契数列

求斐波那契数列的第$n$项。
传统的递归算法有很多计算是重复的，时间复杂度以$n$的指数的方式递增。
改进方式：把上一步的答案存下来，用到下一步即可。

public class Solution {
    public int Fibonacci(int n) {
        int n1 = 0;
        int n2 = 1;
        if (n == 0) {
            return n1;
        } else if (n == 1) {
            return n2;
        }
        for(int i = 2; i <= n; i++) {
            int temp = n1;
            n1 = n2;
            n2 = temp + n2;
        }
        return n2;
    }
}

在O(1)时间删除链表节点

分析可能，有可能被删除的节点是头节点，那么我们先建一个虚拟节点，防止头节点被删，让虚拟节点的下一个节点指向头结点。然后循环遍历，调过那个要删除的节点，直接把上一个节点指向要被删除节点的下一个节点即可。代码

反转链表

定义三个指针，分别指向当前遍历到的节点、它的前一个节点及后一个节点。代码

合并两个排序的列表

如果某一个链表为空，那么合并后就是那个不为空的链表，接下来，从头结点开始判断两个链表节点值的大小，进行合并。递归地进行此过程。MergeSortedLists

从上往下打印二叉树

层次遍历二叉树，在纸上画一棵树，分析它的运行过程，可以发现它是一个先进先出的结构，那么我们可以用队列进行实现。每次打印一个节点，如果它存在叶子节点，那么把它的叶子节点存入队列中。接下来在队列头部取出一个节点，打印，不断循环。

二叉搜索树与双向链表

二叉搜索树的中序遍历是从小到大的排序，那么我们把这个序列转化为双向链表即可。

字符串的排列

把字符串分为两部分：第一部分，第一个字符的位置记为A，第二部分，除了A之外，字符串右边剩余的部分，记为B。把位置A的字符与B部分中的每一个字符进行逐一交换。递归地完成交换，直至字符串末尾。

数组中出现次数超过一半的数字

1. 基于快排中Partition函数的O(n)算法
   使用Partition函数找到数组中的中位数即可，即让Partition的返回的index为数组的中间那个数的位置，即为所得答案。
2. 利用数组特点
   遍历数组，遍历的时候保存两个值，一个是数组的数字，一个是次数。当遍历到下一个数字时，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为0，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字的出现次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

丑数

创建数组保存已经找到的丑数，用空间换时间的解法。
每一个丑数都是前面的丑数乘以2、3或者5得到的。

两个链表的第一个公共节点

1. 蛮力法(一一比较)
2. 分析题目，公共节点而部分重合的，只可能从链表尾部开始往前的一部分地方重合，是个Y型的样子，而不可能是X型的，那么我们从链表尾部开始比较，但是链表是从前往后遍历的，所以我们利用栈“后进先出”的特点。遍历链表的时候把节点存到栈中，全部入栈后，然后再从栈中取出一一比较。
3. 先遍历每个链表，知道哪个链表比较长，再让长的链表先遍历它们间的步数差，然后它们两个一起遍历，第一个相同的节点就是它们第一个公共节点。

数字在排序数组中出现的次数

利用二分查找的思想，找到第一次出现的位置，和最后一次出现的位置，然后相减。

和为s的两个数字，和为s的连续正数序列

利用两个指针。