面试:老师讲的递归解决斐波那契数列真的好吗

简介: 在搞「模拟面试」的日子,我发现大家普遍有个问题就是,感觉自己的能力总是到了瓶颈期,写了好几年代码,感觉只是会的框架比以前多了而已。去大公司面试,屡战屡败,问失败原因,大多数人的答案都是,在三面数据结构与算法的时候,直接就挂了。

在搞「模拟面试」的日子,我发现大家普遍有个问题就是,感觉自己的能力总是到了瓶颈期,写了好几年代码,感觉只是会的框架比以前多了而已。去大公司面试,屡战屡败,问失败原因,大多数人的答案都是,在三面数据结构与算法的时候,直接就挂了。

而不少人表示,我数据结构与算法潜心修炼,把书都啃烂了,倒背如流,但每次一面试,咋就是不会呢?

归根结底,还是思维训练的问题,很多人知其然而不知其所以然,所以,南尘就尽量地贴近大家的常态化思维去帮助大家训练算法吧。

昨天已经给大家预告了,不知道小伙伴们下来有没有去自己尝试处理。但不管怎样,要想训练好算法,但听别人讲不去思考,是肯定没用的。好了废话不多说,进入正题!

来到今天的面试题

面试题:一直青蛙一次可以跳上 1 级台阶,也可以跳上 2 级,求该青蛙跳上 n 级的台阶总共有多少种跳法。

题目来源于《剑指 Offer》

一看这道题,好像没啥思路,感觉和我们的数据结构和常用的算法好像一点都不沾边。

但这看起来就像一道数学题,而且似乎就是高考数学的倒数第一题,所以我们就用数学来做吧。

数学中有个方法叫「数学归纳法」,我们这里就可以巧妙用到。

  1. 当 n = 1 时,青蛙有 1 种跳法;
  2. 当 n = 2 时,青蛙可以选择一次跳 1 级,跳两次;也可以选择一次跳 2 级;青蛙有 2 种跳法;
  3. 当 n = 3 时,青蛙可以选择 1-1-1,1-2,2-1,青蛙有 3 种跳法;
  4. 当 n = 4 时,青蛙可以选择 1-1-1-1,1-1-2,1-2-1,2-1-1,2-2,青蛙有 5 种跳法;
  5. 似乎能得到 f(3) = f(2) + f(1),f(4) = f(3) + f(2),这是 f(n) = f(n-1) + f(n-2) 的节奏?我们得用 n = 5 验证一下。
  6. 当 n = 5 时,青蛙可以选择 1-1-1-1-1,1-1-1-2,1-1-2-1,1-2-1-1,2-1-1-1,1-2-2,2-1-2,2-2-1,青蛙有 8 种跳法,f(5) = f(4) + f(3) 成立。

这是最笨的方法了,得出了这确实就是一个典型的斐波那契数列,唯一不一样的地方就是 n =2 的时候并没有 f(2) = f(0) + f(1)。

稍微有点思维能力的可能更简单。

  1. n = 1 ,青蛙有 1 种跳法;
  2. n = 2 ,青蛙有 2 种跳法;
  3. n = 3,青蛙在第 1 级可以跳 1 种,后面 2 级相当于 f(3-1) = f(2),还有一种就是先跳 2 级,然后后面 1 级有 f(3-2) = f(1) 种跳法,可以得出 f(3) = f(2) + f(1);
  4. ...
  5. 当取 n 时,青蛙在第一次跳 1 级,后面的相当于有 f(n-1) 种跳法;假设第一次跳 2 级,后面相当于有 f(n-2) 种跳法;故可以得出 f(n) = f(n-1) + f(n-2);

这样思考可能更不容易出错吧,这就是思维的提炼过程,可见我们高考常考的「数学归纳法」是多么地有用。

既然能分析出这是一道典型的斐波那契数列了,我想教科书都教给大家方法了,不过一定要注意 n = 2 的时候,正常的斐波那契数列值应该是 1,而我们是 2。大多数人肯定会写出下面的代码:

public class Test09 {

    private static int fn(int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        else
            return fn(n - 1) + fn(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fn(1));
        System.out.println(fn(2));
        System.out.println(fn(3));
        System.out.println(fn(4));
    }
}

我们教科书上反复用这个问题来讲解递归函数,但并不能说明递归的解法是最适合这个题目的。当我们暗自窃喜完成了这道面试题的时候,或许面试官会告诉我们,上面的这种递归解法存在很严重的效率问题,并让我们分析其中的原因。

我们以求 fn(10) 为例,要想求得 fn(10),需要先求得 fn(9) 和 fn(8);同样,要求得 fn(9),需要先求得 fn(8) 和 fn(7)......

这存在一个很大的问题,我们一定会去重复计算很多值,我们一定得想办法把这个计算好的值存放起来。

避免重复计算

既然我们找到了问题所在,那改进方法自然是信手拈来了。我们目前的算法是「从大到小」计算,而我们只需要反向「从小到大」计算就可以了。我们根据 fn(1) 和 fn(2) 计算出 fn(3),再根据 fn(2) 和 fn(3) 计算出 fn(4)......

很容易理解,这样的算法思路时间复杂度是 O(n),实现代码如下:

public class Test09 {

    private static long fn(int n) {
        if (n <= 0)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        long prePre = 1, pre = 2;
        long result = 0;
        for (int i = 3; i <= n; i++) {
            result = prePre + pre;
            prePre = pre;
            pre = result;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fn(1));
        System.out.println(fn(3));
        System.out.println(fn(50));
        System.out.println(fn(100));
    }
}

上面的代码,一定要注意做了一点小修改,我们把返回值悄悄地改成了 long ,因为我们并不能保证客户端是否会输入一个比较大的数字,比如:100,这样,如果返回值为 int,一定会因为超出了最大值而显示错误的,解决方案就是把值换为更大容量的 long。但有时候你会发现,long 的容量也不够,毕竟整型和长整型,它都会有最大显示值,在遇到这样的情况的时候。我们最好和面试官交流一下,是否处理这样的情况。如果一定要处理这样的情况,那么可能你就得用 String 来做显示处理了。

其实在《剑指 Offer》上还有时间复杂度为 O(logn) 的解法,但因为不够实用,我们这里也就不讲解了,主要还是我们解题的算法思路训练。如果真的很感兴趣的话,那就请移步《剑指 Offer》吧。反正你在公众号后台回复「剑指Offer」就可以拿到 PDF 版本的。

总结

今天的面试讲解就到这吧,大家一定要学会自己去独立思考,训练自己的思维。简单回顾一下我们本周所学习的内容,我们下周再见!

目录
相关文章
|
2月前
|
测试技术
【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
【一刷《剑指Offer》】面试题 9:斐波那契数列(扩展:青蛙跳台阶、矩阵覆盖)
|
11月前
|
存储 Java
第二季:5公平锁/非公平锁/可重入锁/递归锁/自旋锁谈谈你的理解?请手写一个自旋锁【Java面试题】
第二季:5公平锁/非公平锁/可重入锁/递归锁/自旋锁谈谈你的理解?请手写一个自旋锁【Java面试题】
36 0
|
2月前
|
算法 C++
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
数据结构和算法面试题:实现一个函数,将一棵二叉树转换为它的镜像。(递归或者非递归实现)
24 0
|
2月前
|
Rust 前端开发 JavaScript
【面试题】JavaScript中递归的理解
【面试题】JavaScript中递归的理解
|
2月前
剑指Offer LeetCode 面试题10- I. 斐波那契数列
剑指Offer LeetCode 面试题10- I. 斐波那契数列
29 0
|
11月前
|
Java
第一季:5递归与迭代【Java面试题】
第一季:5递归与迭代【Java面试题】
42 0
|
存储
剑指Offer - 面试题10:斐波那契数列
剑指Offer - 面试题10:斐波那契数列
65 0
|
JavaScript API 容器
一道价值25k的腾讯递归组件面试题(Vue3 + TS 实现)
小伙伴们好久不见,最近刚入职新公司,需求排的很满,平常是实在没时间写文章了,更新频率会变得比较慢。 周末在家闲着无聊,突然小弟过来紧急求助,说是面试腾讯的时候,对方给了个 Vue 的递归菜单要求实现,回来找我复盘。 正好这周是小周,没想着出去玩,就在家写写代码吧,我看了一下需求,确实是比较复杂,需要利用好递归组件,正好趁着这个机会总结一篇 Vue3 + TS 实现递归组件的文章。
|
SQL
SQL面试题:类递归计算
最近遇到一个比较有意思的SQL题,看似需要使用递归计算,其实不然,可以使用窗口函数解决
334 0
JavaSE面试题——方法的递归与迭代
JavaSE面试题——方法的递归与迭代
JavaSE面试题——方法的递归与迭代