LintCode斐波纳契数列题目:分析小结

题目:

查找斐波纳契数列中第 N 个数。 所谓的斐波纳契数列是指: 前2个数是 0 和 1 。 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

样例 给定1,返回0

给定2,返回1

给定10,返回34

分析

开始刷LintCode的第一道题,也是很基础的一道题。 斐波那契数列经常用来讲解递归的例子。 所以可以用递归的方法很方便的解决

递归

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        if(n == 1)
        {
            return 0;
        }
        else if(n == 2)
        {
            return 1;
        }
        else
        {
            return fibonacci(n-1) + fibonacci(n-2); 
        }
    }
}

这是用递归的方法解决,很清晰,几乎是照搬了斐波那契数列的递推式 但是递归算法的时间复杂度太高,提交之后并不通过

捕获.PNG

非递归方法

所以需要尝试非递归方法解决这个问题

class Solution {
    /**
     * @param n: an integer
     * @return an integer f(n)
     */
    public int fibonacci(int n) {
        // write your code here
        if(n == 1)
        {
            return 0;
        }
        else if(n == 2)
        {
            return 1;
        }
        else
        {
            int s1 = 0;
            int s2 = 1;
            int sum = 0;
            int i = 3;
            while(i <= n)
            {
                sum = s1 + s2;
                s1 = s2;
                s2 =sum;
                i++;
            }
            return sum;
        }
    }
}

小结

以上就是斐波那契数列问题。 ** 故不积跬步,无以至千里;不积小流,无以成江海 ** 希望能慢慢坚持下去,从简单到复杂的算法!

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

1131
来自专栏Python小屋

哈夫曼编码原理与Python实现代码(附手动推导过程原稿真迹)

哈夫曼编码依据字符出现概率来构造异字头(任何一个字符的编码都不是其他字符的前缀)的平均长度最短的码字,通过构造二叉树来实现,出现频次越多的字符编码越短,出现频次...

7198
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

2017
来自专栏chenjx85的技术专栏

leetcode-852-山脉数组的峰顶索引

1664
来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

57010
来自专栏JavaEdge

设计模式实战 - 解释器模式(Interpreter Pattern)

● 公式可以运行时编辑,并且符合正常算术书写方式,例如a+b-c ● 高扩展性,未来增加指数、开方、极限、求导等运算符号时较少改动 ● 效率可以不用考虑,晚...

1152
来自专栏数据结构与算法

后缀自动机经典操作

1974
来自专栏小詹同学

Leetcode打卡 | No.015 三数之和

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

1332
来自专栏take time, save time

你所能用到的数据结构(四)

五、如何递,怎样归? 很多人看完递归的原理之后会有这种感觉,喔,这个原理我懂了,然后再找一道其余的题目看一看能不能写的出来,突然发现,我勒个去,还是不会。其实...

34310
来自专栏技术碎碎念

递归与分治之快速排序

分治法就是把一个大问题分解为多个类型相同的子问题,最后把这些子问题的解合并起来就是问题的解。 快速排序(Quicksort)是对冒泡排序的一种改进,采用了分治的...

3056

扫码关注云+社区

领取腾讯云代金券