题解 | #跳台阶扩展问题#
跳台阶扩展问题
http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387
一.题目描述
JZ9 跳台阶扩展问题
题目链接:https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
注意审题:该题青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级.
二.算法1(找规律)
可发现 1，2，4，8，16，32（n=1,2,3,4,5,6）即2^(n-1).找到规律可以求出n阶台阶的方案数了.
class Solution {
public:
int jumpFloorII(int number) {
long long a=2,b=number-1,c=1;
while(b){//用的快速幂求2^(n-1)速度更加快
if(b%2) c*=a;
a*=a;
b/=2;
}
return c;
}
};复杂度:o(logn)
优缺点:实现比较方便,但是规律不容易发现要至少例举到5才可以发现规律
三.算法2(递归)
两式相减得:
得到上述关系式子直接上代码:
class Solution {
public:
int jumpFloorII(int number) {
if(number<= 0)
return -1;
else if(number==1)
return 1;
else{
return 2*jumpFloorII(number-1);
}
}
};复杂度:o(n)
优缺点:实现比较简单,但是利用函数进行推导不容易想到.
查看2道真题和解析