千问 LeetCode 50. Pow(x, n) Python3实现

LeetCode 50. Pow(x, n) 的核心思路是快速幂算法二分求幂。如果直接循环乘 n 次时间复杂度是 O(n)在 n 很大时会超时。快速幂的核心思想是分治如果 n 是偶数x^n (x{n/2})2如果 n 是奇数x^n x cdot (x{(n-1)/2})2这样每次递归或迭代都能将指数减半时间复杂度降为 O(log n)。下面为你提供两种 Python3 的实现方式解法一递归实现最直观体现分治思想class Solution:def myPow(self, x: float, n: int) - float:# 1. 处理负指数的情况if n 0:return 1.0 / self.myPow(x, -n)# 2. 递归终止条件 if n 0: return 1.0 # 3. 分治先计算 x^(n//2) half self.myPow(x, n // 2) # 4. 合并结果根据 n 的奇偶性决定是否需要多乘一个 x if n % 2 0: return half * half else: return half * half * x解法二迭代实现最优避免递归栈溢出利用位运算来检查 n 的最低位是 0 还是 1从而在循环中完成快速幂。class Solution:def myPow(self, x: float, n: int) - float:# 1. 处理负指数if n 0:x 1.0 / xn -nresult 1.0 current_product x # 记录当前的 x^(2^i) # 2. 循环直到 n 变为 0 while n 0: # 如果 n 的最低位是 1说明需要乘上当前的 current_product if n 1: result * current_product # 将 x 平方对应指数减半 current_product * current_product # n 右移一位相当于 n // 2 n 1 return result 核心要点解析负指数处理x^{-n} frac{1}{x^n}。注意 Python 中 -n 不会像 C/Java 那样在 n -2^{31} 时发生整数溢出所以处理起来非常安全。分治降维无论是递归还是迭代核心都是把 O(n) 的乘法次数降到了 O(log n)。例如计算 x^{10}只需要计算 x^2 rightarrow x^4 rightarrow x^8再组合即可。位运算的妙用在迭代法中n 1 等价于 n % 2n 1 等价于 n // 2但位运算在底层执行效率更高。复杂度分析时间复杂度O(log n)循环或递归的次数等于 n 的二进制位数。空间复杂度递归法为 O(log n)系统调用栈迭代法为 O(1)。如果你刚做完这道题强烈建议去体验一下 LeetCode 372. 超级次方它结合了快速幂和模运算是对这道题思想的绝佳进阶