Leetcode题50、Pow(x,n)（Python题解）Facebook面试题

问题：

题目来源：力扣（LeetCode）

leetcode50.Pow(x,n)

难度：中等

分析： 递归和迭代，每次计算问题的一半就可以。 注意n次幂分为单数和双数的情况，也分整数和负数的情况。

解决方法： 1：递归

class Solution: def myPow(self, x: float, n: int) -> float: def quickMul(N): if N == 0: return 1.0 y = quickMul(N // 2) ans = y * y if N % 2 == 0 else y * y * x return ans return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

2：迭代

class Solution: def myPow(self, x: float, n: int) -> float: def quickMul(N): ans = 1.0 # 贡献的初始值为 x x_contribute = x # 在对 N 进行二进制拆分的同时计算答案 while N > 0: if N % 2 == 1: # 如果 N 二进制表示的最低位为 1，那么需要计入贡献 ans *= x_contribute # 将贡献不断地平方 x_contribute *= x_contribute # 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可 N //= 2 return ans return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

迭代法容易越界，因为当N = 1的时候，x_contribute进行了一次多余的计算。 x_contribute用来计算偶数次幂的结果，当N = 1的时候，ans接收x_contribute计算过的偶数次幂的结果，得到答案，ans在开始的时候就将多余的奇数次幂计算在内了。而此时x_contribute多进行了一次循环，容易造成数值的越界。