查找斐波納契數(shù)列中第 N 個數(shù)。
所謂的斐波納契數(shù)列是指：
前2個數(shù)是 0 和 1 。
第 i 個數(shù)是第 i-1 個數(shù)和第i-2 個數(shù)的和。
斐波納契數(shù)列的前10個數(shù)字是：
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用數(shù)組的方式解決：
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];
}
}
}
