1. 斐波那契数列
斐波那契数列是面试中常问的一道算法题。为了避免有些同学不知道，这里先说一下其定义：
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
其公式：
F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
其中F(1) = 1, F(2) = 1
今天我们就来实现这样的一个简单的算法题，看看如何做到简单、高效、优雅。
2. 简单实现
我们先来实现一个初级的版本，从公式来看，很适合使用递归实现，直接甩代码：
private int fibonacci_v1(int n) {
if(n == 0)
return 0;
if(n == 1 || n == 2)
return 1;
return fibonacci_v1(n-1) + (fibonacci_v1(n-2));
}
如果面试的时候这样写，大概率是要凉凉，麻雀虽小五脏俱全。我们还是要考虑一个问题：
- 是否会溢出？
基于此，我们再来一个版本：
private BigInteger fibonacci_v2(int n) {
if(n == 0)
return BigInteger.ZERO;
if(n == 1 || n == 2)
return BigInteger.ONE;
return fibonacci_v2(n-1).add(fibonacci_v2(n-2));
}
写到这里，内心轻蔑一笑，so easy！！！
3. 如何高效
这个时候，面试官问一下，你这个效率怎么样呢？
好，来测试一下：
public static void main(String[] args) {
long currentTimeMillis = System.currentTimeMillis();
Fibonacci fibonacci = new Fibonacci();
for (int i = 0; i < 42; i++) {
System.out.println(fibonacci.fibonacci_v2(i));
}
long currentTimeMillis2 = System.currentTimeMillis();
System.out.println(" cost :" + (currentTimeMillis2-currentTimeMillis));
}
//输出：
cost :12182
才42个，一共花费12s！！！！为什么会这么慢呢？
因为每计算一个数据，都会重新递归去计算之前的数据，这里是指数级别的增长，递归调用的函数开销是非常大的。
有没有快一点的办法呢？当然有：空间换时间
结合我们之前写的HashMap的原理和使用，我们可以把每一步的结果都缓存在HashMap里面，使用的时候去查表，这样就不用递归计算了。直接甩代码：
private Map<Integer, BigInteger> memoizeHashMap = new HashMap<>();
{
memoizeHashMap.put(0, BigInteger.ZERO);
memoizeHashMap.put(1, BigInteger.ONE);
memoizeHashMap.put(2, BigInteger.ONE);
}
private BigInteger fibonacci_v3(int n) {
if (memoizeHashMap.containsKey(n)) {
return memoizeHashMap.get(n);
} else {
BigInteger result = fibonacci_v3(n - 1).add(fibonacci_v3(n - 2));
memoizeHashMap.put(n, result);
return result;
}
}
我们来测试一下效率：
public static void main(String[] args) {
long currentTimeMillis = System.currentTimeMillis();
Fibonacci fibonacci = new Fibonacci();
for (int i = 0; i < 42; i++) {
System.out.println(fibonacci.fibonacci_v3(i));
}
long currentTimeMillis2 = System.currentTimeMillis();
System.out.println(" cost :" + (currentTimeMillis2-currentTimeMillis));
}
//输出：
cost :11
看到没有，一共才11ms，效果大幅度提高，这个就是HashMap当作内存缓存的优势。
如果面试到这里，你已经比一般人想得更远了，内心可以再来一次：
so easy！！！！
4. 如何优雅
这个时候，面试官又问你，既然你使用了HashMap，有没有可能把你的代码写得更优雅一点？
WTF！！！
优雅？excuse me？
How？
答案当然是有的，在Java8以上，HashMap加入了几个新函数：
-
computeIfAbsent
-
puIfAbsent
-
puIfAbsent
-
merge
可以参考一下文章：https://blog.csdn.net/wang_8101/article/details/82191146.
我们这里使用computeIfAbsent，这个函数简单来说，就是,如果map里存在key就什么也不做，直接获取value，没有就通过计算一个值，并返回这个值。代码直接甩出来：
private BigInteger fibonacci_v4(int n) {
return memoizeHashMap.computeIfAbsent(n,
(key) -> fibonacci_v4(n - 1).add(fibonacci_v4(n - 2)));
}
只有一句话实现了，你问面试官，优雅不优雅？
5. 小结
通过本文，了解了斐波那契数列的几种实现方式，特别地我们使用了朴素的思想：空间换时间，对小算法进行了优化，最后还实现了一个比较优雅的版本，编程就是这样，一步一步精益求精。
我在我的Java学习互助群里面也是这样要求大家的。
最后希望文章对你有用。
网友评论