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)