【剑指Offer】斐波那契数列

Posted on | In ,

题目

写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。

效率很低的解法，挑剔的面试官不会喜欢

1
2
3
4
5
6
public int Fibonacci(int n) {
    if (n == 0 || n == 1)
        return n;

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

面试官期待的实用解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int Fibonacci(int n) {
    if (n == 0 || n == 1)
        return n;

    int fib1 = 0;
    int fib2 = 1;

    for (int i = 2; i <= n; i++){
        int current = fib1 + fib2;
        fib1 = fib2;
        fib2 = current;
    }

    return fib2;
}

时间复杂度O(logn)但不够实用的解法

相关题目

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

实现

1
2
3
4
5
6
public int JumpFloor(int target) {
    if (target == 1 || target == 2)
        return target;

    return JumpFloor(target - 1) + JumpFloor(target - 2);
}

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。此时该青蛙跳上一个n级的台阶总共有多少种跳法？

实现

1
2
3
4
5
6
public int JumpFloorII(int target) {
    if (target == 0 || target == 1)
        return 1;

    return 2 * JumpFloorII(target - 1);
}

矩形覆盖

我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2xn的大矩形，总共有多少种方法？

实现

1
2
3
4
5
6
public int RectCover(int target) {
    if (target == 0 || target == 1 || target == 2)
        return target;

    return RectCover(target - 1) + RectCover(target - 2);
}