JZ9 — 变态跳台阶

题目描述

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

题目分析

由题目易得f[n] = f[n-1] + f[n-2] + ... + f[1] + 1
如果不知道这个结论是怎么得到的,可以参考上一题:http://www.guanhaobo.cn/?p=686

f[1] = 1
f[2] = f[1] + 1 = 2 * f[1]
f[3] = f[2] + f[1] + 1 = 2 * f[2]
f[4] = f[3] + f[2] + f[1] + 1 = 2 * f[3]

易得f[n] = 2 * f[n-1]
所以直接递归或递推就可以解决本题,不再赘述。

这里介绍一种更快的方法,由f[n] = 2 * f[n-1]f[1] = 1易得f[n] = pow(2, (n - 1)),即2的n - 1次幂。
计算幂的时候,可以使用快速幂算法加快速度。

例如求350次方:易得50的二进制形式为110010,即50 = 110010B = 100000B + 10000B + 10B,即pow(3, 50) = pow(3, 32) * pow(3, 16) * pow(3, 2)。因此先求出pow(3, 2),再利用pow(3, 2)求出pow(3, 16),最后通过pow(3, 16)求出pow(3, 32)即可。
事实上,易得pow(a, pow(2, n)) = pow(a, pow(2, n-1)) * pow(a, pow(2, n-1)),例如pow(a, 1000B) = pow(a, 100B) * pow(a, 100B).

这个算法的主要思想就是通过指数的二进制形式,巧妙地将结果分解为若干个乘积,即指数的二进制形式下为1的位置对应的值。
basenumber次幂,具体策略如下:
number > 0时,执行以下循环
1. 对number1进行按位与操作。如果等于1,说明number的二进制形式在当前位置为1,令ans = ans * base
2. 令base = base * base
3. 对number进行二进制移位操作,右移一位。即number = number >> 1

C语言实现如下:

// 求base的number次幂
int quickpow(int base, int number)
{
    int ans = 1;
    while (number)
    {
        if (number & 1)
            ans *= base;
        base *= base;
        number >>= 1;
    }
    return ans;
}

我们会发现,循环次数其实就是number的二进制形式的长度,因此时间复杂度为O(log(n))

C++

class Solution
{
public:
    int jumpFloorII(int number)
    {
        int base = 2, ans = 1;
        number--;
        while (number)
        {
            if (number & 1)
                ans *= base;
            base *= base;
            number >>= 1;
        }
        return ans;
    }
};

Java

public class Solution {
    public int JumpFloorII(int target) {
        int base = 2, ans = 1;
        target--;
        while (target > 0) {
            if ((target & 1) == 1)
                ans *= base;
            base *= base;
            target >>= 1;
        }
        return ans;
    }
}

一个回复在 “JZ9 — 变态跳台阶

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部