前言
在这之前的题目大多属于考察数据结构,然后对于 算法 的考查也是很重要的 。
- 有很多的算法都可以通过递归和循环两种方式来实现,虽说前者的实现较为简洁,但是在性能上并不占优。但在面试的时候,如果面试官没有不允许使用递归,还是可以优先使用递归来解决问题,毕竟递归实现简单一些。
- 对于排序和查找也是算法考察的两大重点。其中应该 重点掌握二分查找、归并排序、快速排序 。
- 如果是对二维数组(可能表现为迷宫或棋盘)搜索路径,那么可以考虑回溯法 。
- 如果面试题是求某个问题的最优解,并且问题可以分为多个子问题,且子问题之前存在重叠,那么我们可以使用动态规划解决问题,以避免使用递归而带来很多不必要的重复性计算。
- 如果在求最优解的时候,在分解子问题的时候是不是存在某个特殊的选择,如果采用这个特殊的选择将一定能够得到最优解,那么应该考虑一下贪心算法。
- 最后也需要懂得五种位运算:与、或、异或、左移和右移。
递归的缺陷:由于函数调用是有时间和空间消耗的,因此每一次函数调用,都需要在内存栈中分配空间以保存参数、返回地址和临时变量,并且往栈中压栈和弹出数据都耗时,因此递归效率很低。更严重的是,由于每个进程的栈容量是有限的,因此当递归调用的层级过多,就会超出栈的容量而导致栈的溢出问题。
题目一(斐波那契数列)
题目:求斐波那契数列的第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 级台阶,只有一种跳法;
- 只跳 2 级台阶,可以先跳 1 级,再跳 1 级,也可以一次跳 2 级,所以共有 2 种跳法;
- 那么现在我们考虑跳 n 级台阶的情况,要跳到第 n 级,我们可以从第n-2 级跳一次直接到第 n 级,也可以从 n-1 级开始跳,那么假设 f(n) 表示跳到第 n 级的跳法数,那么f(n)=f(n-1)+f(n-2)。
- 诶,我们发现这个思路长得有点像斐波那契数列,只是一些初始条件不太一样而已,其他做法都相似。那么我们只需把上面的代码做简单修改即可。
算法实现
题目三(变态青蛙跳台阶)
题目:一只青蛙一次可以跳上 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。
算法实现
递归版本
循环版本
移位版本
复杂度分析
- 对于递归版本的斐波那契,由于每次计算都是将问题分为两个子问题,故 T(n)=T(n-1)+T(n-2)+O(1),则 T(n)=O(1.618^n);另外由于空间复杂度取决于递归的深度,那么其空间复杂度为 O(n)。
- 对于循环版本的斐波那契,很明显时间复杂度为O(n),空间复杂度为O(1)。
参考
<<剑指offer2>>