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)