【算法日记】快速幂：关于我知道答案却做不出来这档事

⭐LeetCode第330场周赛，直接卡在了第二题😭，掉大分，学到一手快速幂。

⭐本文包含以下内容：快速幂，快速幂取余。

⭐参考教程：

  • Math.pow(x, n) 这个函数大家应该并不陌生，他就是用来计算 x^n^ 的函数，那么他是怎么实现的呢？
  • 快速幂的讲解推荐大家去看一个视频：50. Pow(x, n) - 力扣（Leetcode）
  • 下面给出代码实现，使用语言：TypeScript

暴力计算

// 直接将x连乘n次即可
// 时间复杂度 O(n)
function myPow(x: number, n: number): number {
    let m: number = 1
    // 遇到负数需要连乘 1/x
    if(n<0) x = 1/x
    for(let i=0;i<Math.abs(n);i++) {
        m*=x
    }
    return m
}

快速幂（理解）

  • 举一个简单的例子
    • 计算 2^4^ 正常来说我们会直接依次连乘 2*2*2*2
    • 我们把他拆成两半来看 (2*2)*(2*2) 我们发现 2*2 仅需计算一次 再将两份相乘即可得到答案 可以减少计算次数
    • 如果n为基数则拆成 两份相乘再乘以 x，例：2^7^ (2*2*2) * (2*2*2) * 2 依然可以减少计算次数
  • 那么我们便可以得到一个公式
    • x为偶数：x^n^ == (x*x)^n/2^
    • x为奇数：x^n^ == (x*x)^n/2^ * x
  • 以上便是快速幂的基本原理，直接带入计算并加入一些特殊情况便可实现快速幂。
// 对 n 进行折半计算，无需重复连乘
// 时间复杂度 O(logn)
function myPow(x: number, n: number): number {
    function myPowHandler(x: number, n: number): number{
        // n 等于 1 返回本身即可
        if(n===1) return x

        // n为奇数需要计算 x**((n-1)/2) * x**((n-1)/2) * x**1
        if(n%2!==0) {
            const half = myPowHandler(x, Math.floor(n/2))
            return half * half * x
        }
        // n为偶数需要计算 x**(n/2) * x**(n/2)
        else {
            const half = myPowHandler(x, Math.floor(n/2))
            return half * half
        }
    }
    // 特殊条件
    // x为1 或 n为0 即返回 1
    if(x===1 || n===0) return 1
    // 负数情况返回 1/x**n
    if(n<0) return 1 / myPowHandler(x, Math.abs(n))
    return myPowHandler(x, n)
};

快速幂（简化）

function myPow(x, n) {
    // 特殊情况判断
    if(n===0) return 1
    else if(n===1) return x
    // 负数计算为倒数的幂
    else if(n < 0) return myPow(1/x, Math.abs(n))
    // 判断奇偶
    // 如果为偶数计算 (x*x)**(n/2)
    // 如果为奇数计算 (x*x)**(n/2)*x
    // 递归结束条件为 n===0 || n===1 （即条件一）
    else return n%2===0 ? myPow(x*x, n/2) : myPow(x*x, Math.floor(n/2))*x
};

猴子碰撞的方法数（快速幂取余）

现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。

img

每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：

  • 顺时针方向的顶点 (i + 1) % n ，或
  • 逆时针方向的顶点 (i - 1 + n) % n 。

如果移动后至少有两个猴子位于同一顶点，则会发生 碰撞 。

返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。

注意，每只猴子只能移动一次。

  • 一下发现规律的我，只有全部顺时针或者全部逆时针两种情况不符合题意
  • 我直接 return ((2**n)) % ((10**9)+7) -2 ，太年轻了，2**n 过大变成了 Infinity 导致数据丢失，绞尽脑汁还是没想出解决方案。
// 观察后发现我们可以知道答案是 x**n - 2
// 并且答案可能过大需要取余
// 由于精度问题 均需要使用BigInt 而不是Number

function monkeyMove(n: number): number {
    const MOD = BigInt(1e9 + 7)
    // 直接把快速幂搬过来加上取余即可
    function myPow(x: bigint, n: bigint) {
        if(n===0n) return 1
        else if(n===1n) return x
        else return n%2n===0n ? myPow(x*x%MOD, n/2n) : myPow(x*x%MOD, n/2n)*x
    };
    // +MOD是因为-2后结果可能为负数
    return Number((myPow(2n, BigInt(n)) - 2n + MOD) % MOD)
};

⭐以上就是全部解题内容啦，如果对你有帮助请给我点个赞吧