查找斐波纳契数列中第 N 个数。
所谓的斐波纳契数列是指：
前2个数是 0 和 1 。
第 i 个数是第 i-1 个数和第i-2 个数的和。
斐波纳契数列的前10个数字是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
注意事项
The Nth fibonacci number won't exceed the max value of signed 32-bit integer in the test cases.
您在真实的面试中是否遇到过这个题？ Yes
样例
给定 1，返回 0
给定 2，返回 1
给定 10，返回 34
解题思路1用递归写
ackage 入门题;
public class Main3 {
public static void main(String[] args) {
int n = 10;
int result = fibonacci(n);
System.out.println(result);
}
public static int fibonacci(int n) {
if (n == 1) {
return 0;
}else if(n == 2){
return 1;
} else {
return fibonacci(n-1)+fibonacci(n-2);
}
}
}
上面的代码超时了用递归
image.png
解决的办法1是定义单个变量：
/**定义三个变量*/
public static int fibonacci3(int n) {
int a = 0;
int b = 1;
int c = 0;
if (n==2) {
return 1;
} else {
for (int i=2;i<n;i++) {
c = a+b;
a=b;
b=c;
}
}
return c;
}
解决办法2用数组的方式解决：
public class Solution {
/**
* @param n: an integer
* @return: an ineger f(n)
*/
public int fibonacci(int n) {
if (n == 1) {
return 0;
} else {
int [] arr = new int[n];
arr[0] = 0;
arr[1] = 1;
for (int i=2;i<arr.length;i++) {
arr[i] = arr[i-1]+arr[i-2];
}
return arr[arr.length-1];
}
}
}
