从斐波那契数列面试算法题讲起：看看如何高效利用HashMap

2019-10-20 本文已影响0人梁孟HE

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学习互助群里面也是这样要求大家的。

最后希望文章对你有用。