LintCode 366. Fibonacci 原创Java参考解答

LintCode 366. Fibonacci 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/fibonacci/

Find the Nth number in Fibonacci sequence.

A Fibonacci sequence is defined as follow:

  • The first two numbers are 0 and 1.
  • The i th number is the sum of i-1 th number and i-2 th number.

The first ten numbers in Fibonacci sequence is:

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

Notice

The Nth fibonacci number won’t exceed the max value of signed 32-bit integer in the test cases.

Example

Given 1, return 0

Given 2, return 1

Given 10, return 34

解题思路

题目是求第n个斐波那契数字。

经典的数学问题。虽然容易,但常在面试中被面试官用来小试牛刀地试探面试者水平。

面试往往要求先写出递归版本,并分析时间复杂度。再优化写出非递归版本。

参考代码(递归)

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

时间复杂度:O(2^n)

参考代码(非递归)

class Solution { 
    /** 
     * @param n: an integer 
     * @return an integer f(n) 
     */ 
    public int fibonacci(int n) { 
        int n1 = 0; 
        int n2 = 1; 
         
        for (int i = 2; i <= n; i++) { 
            int n3 = n1 + n2; 
            n1 = n2; 
            n2 = n3; 
        } 
         
        return n1; 
    } 
}

时间复杂度:O(n)

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注