【Leetcode】剑指Offer10：斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5
提示：
0 <= n <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            f = [0, 1]
            for i in range(2, n+1):
                f[i % 2] =  (f[i % 2] + f[(i + 1) % 2]) % (1e9+7)
            return int(f[n % 2])
1
2
3
4
5
6
7
8
9
10
11

并不是很难的题目，笔者选择了O（1）的空间来解题还能够省一定的内存，但是这样操作在Python里竟然只击败了10%的用户，不禁有些好奇大家的做法。

妙解

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        int result = 0;
        while (--n > 0) {
            result = first + second;
            if (result >= 1000000007) {
                result -= 1000000007;
            }
            first = second;
            second = result;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个解答当中主要有一个小的优化，不选择复杂的取模算法而是选择了减去1e9+7，这种方法可以提高运算效率。

class Solution:
    def fib(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n < 2:
            return n

        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            c = [[0, 0], [0, 0]]
            for i in range(2):
                for j in range(2):
                    c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j]) % MOD
            return c

        def matrix_pow(a: List[List[int]], n: int) -> List[List[int]]:
            ret = [[1, 0], [0, 1]]
            while n > 0:
                if n & 1:
                    ret = multiply(ret, a)
                n >>= 1
                a = multiply(a, a)
            return ret

        res = matrix_pow([[1, 1], [1, 0]], n - 1)
        return res[0][0]

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/solution/fei-bo-na-qi-shu-lie-by-leetcode-solutio-hbss/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

此解法首先需要构建矩阵。

有了矩阵的递推公式之后，问题就被转化为了求解该常数矩阵的快速幂。
快速幂求解过程中有几个小技巧：

• n & 1：位运算快速判断是否为奇数
• n >>= 1：位运算除以2

这题的解法非常巧妙，是矩阵的一个很好的应用。此外，根据评论区的网友说法，字节面试时会要求手撕出O(logn)的解法，说明这类基础题的优化方案的要求会非常的高。