【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 = 1000000007) { result -= 1000000007; } first = second; second = result; } return result; } }

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

class Solution:
    def fib(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        if n  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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

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

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