• 00008.跳台阶及变态跳台阶解法
  • 发布于 1周前
  • 69 热度
    0 评论

题目描述1

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。

题目描述2

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级…… 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

两道跳台阶问题。其实不是很难。起初先找规律。如图所示。





题目描述1和题目描述2的区别在于规律不同。所以这算是斐波那契数列的又一应用了。当然递归也可以。当然简易DP最好。因为递归总是会重复计算很多。贴代码把。递归就不贴了。

public class Solution {
    public int JumpFloor(int target) {
        if(3 > target) {
            return target;
        }
        int prePreNum = 1;
        int preNum = 2;
        int result = 0;
        for(int i = 3; i < target + 1; i++) {
            result = prePreNum + preNum;
            prePreNum = preNum;
            preNum = result;
        }
        return result;
    }
}


然后下面贴变态跳的代码,其实和正常跳相比较的话只需要修改掉逻辑部分,只缓存前一个值即可。在论坛看到一个牛逼写法贴出来。

public class Solution {
    public int JumpFloorII(int target) {
        return 1 << --target;
    }
}
总结:位运算可以这样用。速度和空间最佳。没有之一。看到的时候感觉真的好厉害。所以有时候会感觉这个世界真的有很多好厉害的人阿。啊哈哈哈哈。


用户评论