360门户网站怎样做,软件开发流程八个步骤概要分析,济南做网站的高端品牌,中文网站建设公司50. Pow(x, n)
快速幂算法的目的#xff0c;就是快速计算 x 的 n 次方。基本思路是把 n 视作二进制数#xff0c;则 n 可以被分解为多个 2 的幂次方之和#xff0c;如 12 对应 1100 等于 0∗200∗211∗221∗230*{2^0} 0*{2^1} 1*{2^2} 1*{2^3}0∗200∗211∗221∗23…50. Pow(x, n)
快速幂算法的目的就是快速计算 x 的 n 次方。基本思路是把 n 视作二进制数则 n 可以被分解为多个 2 的幂次方之和如 12 对应 1100 等于 0∗200∗211∗221∗230*{2^0} 0*{2^1} 1*{2^2} 1*{2^3}0∗200∗211∗221∗23即二进制数中每一位的0或1对应的正是系数。因此x12x0∗20x0∗21x1∗22x1∗23{x^{12}} {x^{0*{2^0}}} {x^{0*{2^1}}} {x^{1*{2^2}}} {x^{1*{2^3}}}x12x0∗20x0∗21x1∗22x1∗23。从 n 的二进制形式可以得到系数而对应的 x 的二次幂可以通过 x 自乘得到xx20,x∗xx21,x2∗x2x22......x {x^{{2^0}}},x*x {x^{{2^1}}},{x^2}*{x^2} {x^{{2^2}}}......xx20,x∗xx21,x2∗x2x22......。实现上可以使用递归或者迭代迭代的空间复杂度更优
递归法
class Solution:def myPow(self, x: float, n: int) - float:def quickMul(N: int):if N 0:return 1.0y quickMul(N // 2)return y * y if N % 2 0 else y * y * xreturn quickMul(n) if n 0 else 1.0 / quickMul(-n)迭代法
class Solution:def myPow(self, x: float, n: int) - float:if x 0.0: return 0.0ans 1if n 0: x 1 / xn -nwhile n:if n 1: ans * xx * xn 1return ans372. 超级次方
做这题需要知道的公式是(a∗b)%MOD((a%MOD)∗(b%MOD))%MOD(a*b)\% MOD ((a\% MOD)*(b\% MOD))\% MOD(a∗b)%MOD((a%MOD)∗(b%MOD))%MOD
class Solution:# 快速幂算法def quick_mul(self, x: int, n: int) - int:MOD 1337ans 1while n:if n 1:ans ans * x % MODx x * x % MODn 1return ansdef superPow(self, a: int, b: List[int]) - int:MOD 1337ans 1x a % MODfor y in b[::-1]:ans ans * self.quick_mul(x, y) % MODx self.quick_mul(x, 10)return ans关键是两点一是根据公式增加了多次取模操作MOD二是由于指数存储在了数组中从右到左遍历是低位到高位两种方法一是用一个变量记录当前是第几位则从数组取出来的数与 10 的多少次方相乘二是每次将底数 x 乘以 10 次方这样也相当于指数乘以 10例如 x123(x1)3(x10)2(x100)1{x^{123}} {({x^1})^3} {({x^{10}})^2} {({x^{100}})^1}x123(x1)3(x10)2(x100)1。
