【算法日记】快速幂：关于我知道答案却做不出来这档事
⭐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依然可以减少计算次数
- 计算 2^4^ 正常来说我们会直接依次连乘
那么我们便可以得到一个公式
- x为偶数：x^n^ == (x*x)^n/2^
- x为奇数：x^n^ == (xx)^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
};猴子碰撞的方法数（快速幂取余）
- 我们来看看这道周赛题吧，LeetCode链接：2550. 猴子碰撞的方法数 - 力扣（Leetcode）
现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。
每个猴子同时移动到相邻的顶点。顶点 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)
};⭐以上就是全部解题内容啦，如果对你有帮助请给我点个赞吧
