原创递归数学约 1887 字大约 6 分钟
Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
372. Super Pow | 372. 超级次方 | 🟠 |
今天来聊一道与数学运算有关的题目,力扣第 372 题「超级次方」,让你进行巨大的幂运算,然后求余数。
java 🟢
int superPow(int a, int[] b);
cpp 🤖
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
int superPow(int a, vector<int>& b);
python 🤖
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def superPow(a: int, b: List[int])
go 🤖
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func superPow(a int, b []int) int
javascript 🤖
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var superPow = function(a, b) {
}
要求你的算法返回幂运算 a^b
的计算结果与 1337 取模(mod,也就是余数)后的结果。就是你先得计算幂 a^b
,但是这个 b
会非常大,所以 b
是用数组的形式表示的。
这个算法其实就是广泛应用于离散数学的模幂算法,至于为什么要对 1337 求模我们不管,单就这道题可以有三个难点:
一是如何处理用数组表示的指数,现在 b
是一个数组,也就是说 b
可以非常大,没办法直接转成整型,否则可能溢出。你怎么把这个数组作为指数,进行运算呢?
二是如何得到求模之后的结果?按道理,起码应该先把幂运算结果算出来,然后做 % 1337
这个运算。但问题是,指数运算你懂得,真实结果肯定会大得吓人,也就是说,算出来真实结果也没办法表示,早都溢出报错了。
三是如何高效进行幂运算,进行幂运算也是有算法技巧的,如果你不了解这个算法,后文会讲解。
那么对于这几个问题,我们分开思考,逐个击破。