【算法日记】快速幂:关于我知道答案却做不出来这档事
【算法日记】快速幂:关于我知道答案却做不出来这档事
⭐LeetCode第330场周赛,直接卡在了第二题😭,掉大分,学到一手快速幂。
⭐本文包含以下内容:快速幂,快速幂取余。
⭐参考教程:
Math.pow(x, n)
这个函数大家应该并不陌生,他就是用来计算 x^n^ 的函数,那么他是怎么实现的呢?- 快速幂的讲解推荐大家去看一个视频:50. Pow(x, n) - 力扣(Leetcode)
- 下面给出代码实现,使用语言:TypeScript
暴力计算
1 | // 直接将x连乘n次即可 |
快速幂(理解)
- 举一个简单的例子
- 计算 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^ == (x*x)^n/2^ * x
- 以上便是快速幂的基本原理,直接带入计算并加入一些特殊情况便可实现快速幂。
1 | // 对 n 进行折半计算,无需重复连乘 |
快速幂(简化)
1 | function myPow(x, n) { |
猴子碰撞的方法数(快速幂取余)
- 我们来看看这道周赛题吧,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 导致数据丢失,绞尽脑汁还是没想出解决方案。
1 | // 观察后发现我们可以知道答案是 x**n - 2 |
⭐以上就是全部解题内容啦,如果对你有帮助请给我点个赞吧
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 雪人的小屋!
评论