欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode 查找斐波纳契数列中第 N 个数

程序员文章站 2022-07-03 08:40:55
...

查找斐波纳契数列中第 N 个数。

所谓的斐波纳契数列是指:

  • 前2个数是 0 和 1 。
  • 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

 

 

class Solution {

    /**

     * @param n: an integer

     * @return an integer f(n)

     */

    public int fibonacci(int n) {

        // write your code here

        /*  递归 超时,时间有限制,不能通过测评

        // 测试提示:你的代码运行时间超过了限制,检查你的时间复杂度。

        //   TLE通常是由死循环造成的,思考一下你的时间复杂度是否是最优的。

        if(n>=1){

            if(n==1||n==2){

                return n-1;

            }else{

                return fibonacci(n-1)+fibonacci(n-2);

            }

            

        }else{ 

           return -1;

        }

        */

      

        //枚举法 效率高

        if(n<=0){

            return -1;

        }else if(n==1||n==2){

            return n-1;

        }else{

            int s1=0;

            int s2=1;

            int sum=0;

            for(int i=3;i<=n;i++){

                sum=s1+s2;

                s1=s2;

                s2=sum;

            }

            return sum;

        }

        

    }

}