分析
可推出: F(n) = 2*F(n-1)
递归求解
- class Solution {
- public:
- int jumpFloorII(int number) {
- if(number <= 2)
- {
- return number;
- }
- else
- {
- return 2*jumpFloorII(number-1);
- }
- }
- };
使用移位
其实上面的规律就是一个等比数列, 用公式: An = A1*q^(n-1) 就好, 其中 A1=1, q=2 也就是 An=2^(n-1). 为了进一步优化, 使用移位代替乘, 也就是 1<<(n-1), 代码如下:
- class Solution {
- public:
- int jumpFloorII(int number) {
- int x = 1;
- if(number <= 2)
- {
- return number;
- }
- else
- {
- return x<<(number-1);
- }
- }
- };
变态跳台阶
来源: http://www.bubuko.com/infodetail-3210569.html