【Leetcode】剑指Offer 10- II：青蛙跳台阶问题

140 阅读 0 评论 93 点赞

我是靠谱客的博主霸气白昼，这篇文章主要介绍【Leetcode】剑指Offer 10- II：青蛙跳台阶问题，现在分享给大家，希望可以做个参考。

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：2
示例 2：
输入：n = 7
输出：21
示例 3：
输入：n = 0
输出：1
提示：
0 <= n <= 100
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numWays(self, n: int) -> int:
        if n == 0:
            return 1
        elif n == 1:
            return 1
        else:
            f = [1, 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
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def numWays(self, n: int) -> int:
        if n == 0:
            return 1
        elif n == 1:
            return 1
        else:

            def matrix(a, b):
                c = [[0, 0], [0, 0]]
                for i in range(2):
                    for j in range(2):
                        c[i][j] = int((a[i][0] * b[0][j] + a[i][1] * b[1][j]) % (1e9+7))
                return c

            def power(a, n):
                ret = [[1, 0], [0, 1]]
                while n > 0:
                    if n & 1:
                        ret = matrix(ret, a)
                    n >>= 1
                    a = matrix(a, a)
                return ret
            
            temp = power([[1, 1], [1, 0]], n-1)
            return int((temp[0][0] + temp[0][1]) % (1e9+7))

写的过程算是一个复习，不过快速幂写的依旧磕磕绊绊的，这个板子感觉还是可以简单地背一下。

妙解

复制代码

1
2
3
4
5
6
7
class Solution:
    def numWays(self, n: int) -> int:
        a, b = 1, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007