剑指Offer #09 变态跳台阶（数列推导）

题目来源：牛客网-剑指Offer专题
题目地址：变态跳台阶

题目描述

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

题目解析

这道题有两种比较可靠的方法可以得到规律：

第一种就是观察法，我们先枚举出自己有耐心算得出来的部分，一般是如下表所示：

基于我们强大的数学基础（良好的运气 ）和细致的观察能力（搏一搏的心态 ），我们可以发现规律就是 。

第二种是数学推导法，咋们当然还是信奉科学（玄学 ）的方法。

设该青蛙跳上一个 级的台阶总共有 种跳法，则由题意可得

由后面 得，

是首项为 ，公比为 的等比数列，即 。

公式都有了，解决起来就简单了，这里给大家提供三种实现方式。

方法一：
直接上快速幂的模板，的时间复杂度解决问题，妥妥的。

public class Solution {
    private int quickPow(int a, int n) {
        int ans = 1;
        while (n != 0) {
            if (n % 2 == 1) {
                ans *= a;
            }
            a *= a;
            n /= 2;
        }
        return ans;
    }
    public int JumpFloorII(int target) {
        return quickPow(2, target - 1);
    }
}

想学快速幂的小伙伴可以看这篇博客：数论基础之快速幂（详细教程）

方法二：
调用Math类中的求幂方法pow，再进行强制类型装换，同样可以得到正确的结果。

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

方法三：
利用位运算实现，不熟位运算的小伙伴可以看这篇博客：C++描述的位运算总结

public class Solution {
    public int JumpFloorII(int target) {
        return 1 << (target - 1);
    }
}