入门题3- 斐波纳契数列

查找斐波纳契数列中第 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];
        }
    }
}