《剑指Offer》跳台阶扩展问题（Java）

时空限制

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M 热度指数：612837

题目要求

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
示例：输入3 返回4

分析

在n级范围内，青蛙可以往上跳任意一个台阶。
跳到第n阶的分为经过n-1阶和不经过n-1阶的。
用F[n]表示跳到n级台阶的总数。
经过n-1阶到n级的有F[n-1]种。
不经过n-1阶的等价于有n-1个台阶，即F[n-1]种。
F[n] = 2*F[n-1]，而且F[1] = 1。
由此可以得到F[n] = 2^(n-1)。

代码

普通写法也能过，不过要主义的是，pow函数的参数和返回值类型都是double类型。建议自己写一个。

public class Solution {
public int jumpFloorII(int target) {
return (int)Math.pow(2,target-1);
}
}

快速幂写法，要注意会不会爆数据类型。

public class Solution {
public int jumpFloorII(int target) {
return (int)Math.pow(2,target-1);
}
public int pow(int a,int b){
int base = a,res = 1;
while(b>0){
if( (b&1) == 1 ) res *= base;
base = base * base;
b >>= 1;
}
return res;
}
}

最后

以上就是生动舞蹈为你收集整理的《剑指Offer》跳台阶扩展问题（Java）的全部内容，希望文章能够帮你解决《剑指Offer》跳台阶扩展问题（Java）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。