第8题
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）
思路
开始想的是函数的递归调用，因为每次有两种情况跳一步或两步，所以n级台阶的跳法应该等于n-1级台阶的跳法加n-2级台阶的跳法，见代码段1。
运行发现超时，然后想到这就是斐波那契数列的变形，函数之间的嵌套调用非常麻烦，所以改成了代码段2的形式，通过测试。
代码1
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, number): # write code here def oneStep(n): if n == 1: return 1 elif n == 2: return 2 else: return oneStep(n-1) + oneStep(n-2) if number == 0: return 0 return oneStep(number)
代码2
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# -*- coding:utf-8 -*- class Solution: def jumpFloor(self, number): # write code here s = 0 s1 = 1 s2 = 2 if number <= 2: return number for i in range(number-2): s = s1 s1 = s2 s2 = s+s1 return s2
第9题
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路
还是递归，第n级台阶的跳法等于前面所有台阶跳法的累加加上1（一步到位）。最后发现结果等于2^（n-1），-_-||
递归代码
复制代码
1
2
3
4
5
6
7
8
9
10
11# -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, number): # write code here if number <=2: return number l = [1 for i in range(number)] for i in range(1,number): l[i] = sum(l[0:i])+1 return l[-1]
最后
以上就是优雅茉莉最近收集整理的关于牛客网剑指Offer 第8、9题：跳台阶 python的全部内容，更多相关牛客网剑指Offer内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复