专栏首页小浩算法《剑指offer》第九天:斐波那契数列

《剑指offer》第九天:斐波那契数列

❝问:为什么程序员总是分不清万圣节和圣诞节? 答:因为 Oct 31 == Dec 25。❞

斐波那契数列

题目描述

大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第 n 项(从 0 开始,第 0 项为 0)。n<=39

参考资料

解法

解法一

采用递归方式,简洁明了,但效率很低,存在大量的重复计算。

                  f(10)
               /        \
            f(9)         f(8)
          /     \       /    \
       f(8)     f(7)  f(7)   f(6)
      /   \     /   \ 
   f(7)  f(6)  f(6) f(5)
public class Solution {
    /**
     * 求斐波那契数列的第n项,n从0开始
     * @param n 第n项
     * @return 第n项的值
     */
    public int Fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        // 递归调用
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

解法二

从下往上计算,递推,时间复杂度 O(n)

public class Solution {
    /**
     * 求斐波那契数列的第n项,n从0开始
     * @param n 第n项
     * @return 第n项的值
     */
    public int Fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        int[] res = new int[n + 1];
        res[0] = 0;
        res[1] = 1;
        for (int i = 2; i <= n; ++i) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[n];

    }
}

测试用例

  1. 功能测试(如输入 3、5、10 等);
  2. 边界值测试(如输入 0、1、2);
  3. 性能测试(输入较大的数字,如 40、50、100 等)。

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:脑筋急转弯算法题目(???)

    分享这道题目的原因,是因为有很多同学,在拿到题目的一瞬间,如果发现题目很长,然后自己就慌了。其实,对于这种题目,如果认真的分析下去,非常简单。

    程序员小浩
  • 漫画:贼简单的题目,但百分之99%的人都不会

    今天是小浩算法“365刷题计划”第53天。为大家分享一道本应很简单的题目,但是却因增加了特殊条件,而大幅增加了难度。话不多说,直接看题。

    程序员小浩
  • 漫画:位运算技巧整理汇总+一道被嫌弃的题目

    今天是小浩算法“365刷题计划”第65天。这两天总有人来问我,做公众号赚了多少钱,或者就是怎么能和你一样,2个月就做到7000粉丝。说实话,至少到目前为止,我一...

    程序员小浩
  • 从源代码到Runtime发生的重排序编译器重排序指令重排序内存系统重排序阻止重排序

     源代码和Runtime时执行的代码很可能不一样,这是因为编译器、处理器常常会为了追求性能对改变执行顺序。然而改变顺序执行很危险,很有可能使得运行结果和预想的不...

    用户1174983
  • LeetCode 242. 有效的字母异位词

    进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?

    freesan44
  • PTA 7-2 二叉搜索树的结构(30 分)

    7-2 二叉搜索树的结构(30 分) 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它...

    Kindear
  • Leetcode#70. Climbing Stairs(爬楼梯)

    武培轩
  • 剥开比原看代码15:比原是如何转帐的

    Gitee地址:https://gitee.com/BytomBlockchain/bytom

    比原链Bytom
  • Java中使用方法的注意事项

    一只胡说八道的猴子
  • Android 内存泄漏分析心得

    本文通过 QQ 和 Qzone 中内存泄漏实例来讲 android 中内存泄漏分析解法和编写代码应注意的事项。

    QQ空间开发团队

扫码关注云+社区

领取腾讯云代金券