limanting 的个人博客

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意： 给定 n 是一个正整数。

我的答案

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    if (n < 3) {
        return n;
    }
    let prePre = 1;
    let pre = 2;
    for (let i = 3; i < n; i++) {
        const temp = pre;
        pre = pre + prePre;
        prePre=temp;
    }
    return prePre + pre;
};

这是一个典型斐波那契数列。（用递归会有很多冗余计算）

除了斐波那契数列的方法，还有一个方法就是快速幂。

这里扩展一下快速幂。

题目： 求m^n 。求m的n次方。

解法思路，用尽量少的次数算到结果，不去冗余计算。

var climbStairs = function (n) {
    let m = 4;

    let ans = 1;
    let x = m;
    while(n) {
        let a = n%2;
        n = parseInt(n/2)
        if(a) ans *= x;
        x = x*x;
    }
    return ans;
};

将n的每个二进制位作为系数，x记录当前m的n次方。