剑指Offer-变态跳台阶

发表于 | 分类于

题目描述

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

解题思路

经过之前的跳台阶一题，我也有了一定的经验教训，直接采用数学归纳法来做这题。很快便得到了递推的公式，result = 2^(number-1)。不再赘述，这题的关键便是找到规律，根据数学归纳法总结公式。

1
2
3
4
5
6
7
8
class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2,number-1);
        
        //int a=1; return a<<(number-1);
    }
};

看到有人说用移位操作更快，但其实比我直接调用pow来写慢了1ms。哈哈哈~