前言

在这之前的题目大多属于考察数据结构，然后对于 算法 的考查也是很重要的 。

1. 有很多的算法都可以通过递归和循环两种方式来实现，虽说前者的实现较为简洁，但是在性能上并不占优。但在面试的时候，如果面试官没有不允许使用递归，还是可以优先使用递归来解决问题，毕竟递归实现简单一些。
2. 对于排序和查找也是算法考察的两大重点。其中应该 重点掌握二分查找、归并排序、快速排序 。
3. 如果是对二维数组(可能表现为迷宫或棋盘)搜索路径，那么可以考虑回溯法 。
4. 如果面试题是求某个问题的最优解，并且问题可以分为多个子问题，且子问题之前存在重叠，那么我们可以使用动态规划解决问题，以避免使用递归而带来很多不必要的重复性计算。
5. 如果在求最优解的时候，在分解子问题的时候是不是存在某个特殊的选择，如果采用这个特殊的选择将一定能够得到最优解，那么应该考虑一下贪心算法。
6. 最后也需要懂得五种位运算：与、或、异或、左移和右移。

递归的缺陷：由于函数调用是有时间和空间消耗的，因此每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址和临时变量，并且往栈中压栈和弹出数据都耗时，因此递归效率很低。更严重的是，由于每个进程的栈容量是有限的，因此当递归调用的层级过多，就会超出栈的容量而导致栈的溢出问题。

题目一(斐波那契数列)

题目:求斐波那契数列的第n项。写一个函数，输入n，求斐波那契(Fibonacci)数列的第 n 项。斐波那契的定义如下：
F0=0;F1=1;Fn=Fn-1+Fn-2(n>=2)

递归实现

循环实现

循环实现的关键在于，我们设置了一个 a和b 变量分别来记录之前计算过的 f(n-2) 的值和 f(n-1) 的值，以便可以在下一次计算 f(n) 时使用，避免了子问题重复计算的问题。
其实此题也是动态规划思想的最简单应用。

题目二(青蛙跳台阶)

一指青蛙依次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级台阶总共有多少种跳法。

算法思路

1. 最简单的情况，只跳 1 级台阶，只有一种跳法；
2. 只跳 2 级台阶，可以先跳 1 级，再跳 1 级，也可以一次跳 2 级，所以共有 2 种跳法；
3. 那么现在我们考虑跳 n 级台阶的情况，要跳到第 n 级，我们可以从第n-2 级跳一次直接到第 n 级，也可以从 n-1 级开始跳，那么假设 f(n) 表示跳到第 n 级的跳法数，那么f(n)=f(n-1)+f(n-2)。
4. 诶，我们发现这个思路长得有点像斐波那契数列，只是一些初始条件不太一样而已，其他做法都相似。那么我们只需把上面的代码做简单修改即可。

算法实现

题目三(变态青蛙跳台阶)

题目：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级……它也可以跳上 n 级台阶，此时青蛙跳上一个 n 级的台阶总共有多少种跳法。

算法思路

假设青蛙跳到 n 级台阶的跳法数为f(n),那么

1. 青蛙可以从第n-1级跳到n级，共有f(n-1)种跳法；  
2. 青蛙也可以从第n-2级跳到n级，共有f(n-2)种跳法;  
3. 青蛙也可以从第n-3级跳到n级，共有f(n-3)种跳法;  
4. 依次类推...直到青蛙从第1级跳到n级，共有f(1)种跳法；  
5. 因此青蛙跳到n级的跳法为以上跳法数之和。  

f(n)=f(n-1)+f(n-2)+…+f(1);又f(n-1)=f(n-2)+…+f(1)
因此得到关系：f(n)=2*f(n-1)(n>1),当n=1时，跳法数为1。

算法实现

递归版本

循环版本

移位版本

复杂度分析

1. 对于递归版本的斐波那契，由于每次计算都是将问题分为两个子问题，故 T(n)=T(n-1)+T(n-2)+O(1)，则 T(n)=O(1.618^n);另外由于空间复杂度取决于递归的深度，那么其空间复杂度为 O(n)。
2. 对于循环版本的斐波那契，很明显时间复杂度为O(n)，空间复杂度为O(1)。

参考

<<剑指offer2>>

前言

链表的结构简单，它由指针把若干个节点连接成链状结构。那么必然涉及到链表的创建，如何插入节点，如何删除节点等链表操作。由于这些操作思想简单，还可借助画图理解实现，代码量又不多，因而在面试中经常出现。

链表是一种动态的数据结构，在创建链表的时候，我们无需提前知道链表的长度，而是按需为新节点分配内存即可，这样一来空间的利用率就比数组相对高了。

链表的部分操作

链表节点定义

链表尾部加入节点

在上面代码中，函数的第一个参数 head 是一个指向指针的指针(二级指针)。由于此时会改动头指针(形参)，而我们也需要改变头指针对应的实参，那么需要使用二级指针传递，即需要再加一级的指针，这样当对形参(指向头指针的指针)的指向操作时，就相当于对实参(头指针)本身进行的操作。

链表删除节点

题目描述(从尾到头打印链表)

题目：输入一个链表的头结点，从尾到头反过来打印出每个节点的值(不改变链表结构)。

解题思路一

利用栈线性处理。当我们遍历链表的时候是从头开始访问元素，而输出的时候确要从后面访问的元素先输出，由此联想到栈的特性—后进先出。那么一旦我们访问一个节点就将其入栈，遍历结束后再统一出栈即可逆序输出链表节点。

解题思路二

利用递归的思想。我们每访问一个节点的时候，先递归输出它后面的节点，再输出该节点本身，这样链表的输出结果就反过来了。但是，一旦链表过长，会导致递归层级过深。

算法实现

算法实现一

算法实现二

复杂度分析

解题思路一中，对链表和栈分别仅遍历一次，时间复杂度为 O(n),由于借助了栈，其递归深度为O(n),因而空间复杂度为 O(n)；

解题思路二同上(递归本质上一个栈的结构)。

参考

<<剑指offer2>>

前言

树是一种在实际编程中经常遇到的数据结构。它的逻辑结构很简单：除了根节点以外，每个节点只有一个父节点；除叶节点之外所有节点都有一个或多个子节点。父节点和子节点之间用指针链接。由于树会涉及到大量的指针，因此与树有关的面试题成为了面试官的青睐。
那么需要掌握哪些？就其中一部分来说，关于树的三大遍历方式：前序遍历、中序遍历、后序遍历都必须掌握，并且由于每种遍历方式都有递归和循环两种实现方式，因此我们需要掌握三种遍历六种实现方式。

后期需要掌握的我们后面再提…

题目描述(重建二叉树)

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。(假设输入的前序遍历和中序遍历的结果中都不含重复的数字)

解题思路

首先，重建一棵二叉树，我们可以通过树的两种遍历方式推出树的结构，其中中序遍历是必不可少的序列。
题目给定的是前序遍历和中序遍历，我们知道在前序序列中第一个值root 一定是根节点，而这个 root 所在的中序序列中也是根节点,那么根据前序遍历的特性—先根再左再右，我们知道左右子树的序列一定从前序序列的root的下一个位置开始，而中序遍历的特性是—先左再根再右,那么，对于中序序列，左子树的中序序列从第一个位置到 root 的前一位置的范围内，而右子树的中序序列则从 root 的下一位置到末位置。再者，无论是前序序列还是中序序列，前序序列的左子树序列长度一定等于中序序列的左子树序列长度，右子树亦是。最后其实我们分别得到了 root 节点的左子树对应的前序序列和中序序列，以及右子树对应的前序序列和中序序列。

关键的地方来了，我们还需要对左子树和右子树进行重建二叉树，我们发现这个过程已经在以根节点为 root 的二叉树上走过了，只是序列长度缩短了，那么我们其实可以再次调用一次这个过程(函数)，只要确定左右子树前序和中序序列的范围即可，那么这个过程其实就是利用树的递归特性。而递归的出口就是处理好叶节点的创建。
一个形象的图例:

算法实现

建立树的数据结构

重建二叉树

复杂度分析

时间复杂度

每次在中序遍历序列中找到根节点的位置需要 O(n) 的查找时间。
则T(n)=2T(2/n)+O(n),(两个子问题的时间加中序序列上的查找时间)那么T(n)=O(nlogn)。

空间复杂度

由于每个节点都会被递归到，所以递归栈需要 O(n) 的空间。

参考

<<剑指offer2>>

前言

说到字符串，其实在 C/C++ 中字符串都是以'\0'作为结尾标志。这样做的优点是容易找到字符串尾部，而缺点则是每个字符串额外多了一个字符的内存开销(1 字节),最后计算字符串的实际长度时会比原来多1。

另外，为了节省内存，C/C++ 把常量字符串存储到单独的内存区域，因此，当多个指针赋值给相同的常量字符串时，这些指针所指向的内存地址是相同的。

最后，注意字符数组容量的长度以及字符串实际长度的区别。

题目描述(替换空格)

请实现一个函数，把字符串中的每个空格替换成”%20”。例如，输入 “We are happy.”，则输出 “We%20are%20happy.”。

解题思路

常规思路

我们可以从左往右扫描字符串中的每个字符，但遇到空格的时候，先把空格之后的所有字符统一向后移动两个字符，这样一来刚好空出三个位置，然后再依次填入三个字符’%’,’2’,’0’,接下来，继续查找空格字符，继续执行相同操作。

此方法的缺点是时间复杂度较高,还不是最优的情况，达到了O(n^2)。其实，这种情况有点类似直接插入排序法的操作。对于每个空格的字符，需要移动后面O(n)个字符，那么对于含有O(n)个空字符的字符串而言，总的时间复杂度为O(n^2)。

终极思路

常规思路中的缺点在于，当我们遇到一次空格，然后移动一次后面的所有字符，此时我们无法保证这些字符在之后不会被再次移动。而我们要寻找的就是能不能让移动的这些字符一次就能确定其最终的位置？

常规思路中，是从前往后扫描字符，那么从后往前扫描字符呢。
首先，我们应该统计非空字符的个数，以及空格的个数，那么将一个空格替换为三个字符，原数组长度将增加 2，最后我们得到了字符串中空格都替换成 “%20”所需的长度。

那么，当我们从后往前扫描时，我们先确定替换之后字符串的最终长度。然后利用两个指针 P1和P2 在数组后面复制和替换。当 p1遇到非空字符，则将 p1 所指的元素复制到 p2所指的位置，然后p1、p2继续向前更新指针；当p1 遇到空字符时，将”%20”倒序依次从 p2 处往前插入,接下来，p1、p2 继续向前更新指针，重复上述过程，直至完成替换。具体形象的操作见下图。

算法实现

复杂度分析

我们先用第一个 while 遍历了字符串，耗时约 O(n),第二个 while 中我们主要是移动和插入元素，由于每个元素最多仅移动一次，因此耗时也约 O(n),那么总的时间复杂度为 O(n)=O(n)+O(n)。空间复杂度为 O(1)。

参考

<<剑指offer2>>

前言

二维数组是数组的数组，它在内存中占据连续的空间。在内存中从上到下存储各行元素，在同一行中按照从左到右的顺序存储。因此访问二维数组中的元素时，我们可以根据行号和列号计算出相对于首地址的偏移量。

题目描述(二维数组中的查找)

题目:在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有这个整数。

解题思路

首先，题目的特殊性在于，无论哪一行哪一列都是递增有序的。因此，假如我们从二维数组的最右上角元素 m 开始查找。首先如果刚好找到，则返回，否则，如果待找元素 nm，则 n 一定不会出现在 m 元素所在的行，那么我们就可以剔除 m 所在的行。再接着，只要一直循环比较下去，直到找到或者找不到为止。
算法的另一个思路是：也可以选取从数组的左下角元素开始比较。

算法实现

复杂度分析

时间复杂度

考虑最复杂的情况，即从右上角开始，剔除 m 行，又剔除 n 列，没找到元素，那这样的时间复杂度达到 O(m+n)。

空间复杂度

操作在原数组上进行，空间复杂度为O(1)。

参考

<<剑指offer第二版>>