Topic本题出自LeetCode第50题，大致意思是给定x（浮点数）和n（整数），求x的n次方。SolutionViolentsolution暴力解...当然直接把x乘以n次。注意，如果n为负数，必须先计算x的倒数，再乘以-n次。类解决方案：defmyPow(self,x:float,n:int)->float:ifn==0:return1ifn<0:returnmyPow(1/x,-n)ans=1foriinrange(n):ans*=xreturnans但是显然当n的绝对值很大的时候，会有很可怕的时间消耗，这是没有必要的。快速幂算法递归实现从小学数学我们可以很容易的知道myPow(x,2n)=myPow(x,n)*myPow(x,n)，所以对于给定的我们只需要计算它的n/2次n注意如果n是奇数，比如n=5，先计算n//2=2，向下舍入，然后计算myPow(x,5)=myPow(x,2)*myPow(x,2）*X。这很容易将时间复杂度降低到O(logn)级别。代码不多说了：classSolution:defmyPow(self,x:float,n:int)->float:ifn==1:returnxifn==0:return1ifn<0:returnself.myPow(1/x,-n)returnself.myPow(x,n//2)**2如果n%2==0elseself.myPow(x,n//2)**2*xiterationsLeetCode官方实现也提供了快速幂迭代的实现，将空间复杂度从O(logn)降低到O(1)。思路也很巧妙，供大家参考：classSolution:defmyPow(self,x:float,n:int)->float:defquickMul(N):ans=1.0#贡献初始值为xx_contribute=x#ComputeanswerwhileN>0:ifN%2==1:#如果N的二进制表示的最低位为1，则需要计入贡献ans*=x_contribute#贡献会不断平方x_contribute*=x_contribute#舍弃N的二进制表示的最低位，这样我们每次只需要判断最低位为N//=2returnansreturnquickMul(n)ifn>=0else1.0/quickMul(-n)
