LeetCode如何实现Pow(x,n)

# LeetCode如何实现Pow(x,n)

## 问题概述

LeetCode上的[Pow(x, n)](https://leetcode.com/problems/powx-n/)问题要求我们实现计算x的n次幂（即x^n）的函数。这个问题看似简单，但需要考虑多种边界情况和高效的算法实现。

### 问题描述
- 实现 `pow(x, n)`，即计算x的n次幂
- -100.0 < x < 100.0
- n是32位有符号整数，范围在[-2^31, 2^31 - 1]
- 结果精度保留5位小数

## 暴力解法（不推荐）

最直观的解法是直接循环相乘：

```python
def myPow(x: float, n: int) -> float:
    result = 1
    for _ in range(abs(n)):
        result *= x
    return result if n >= 0 else 1/result

问题：当n很大时（如n=2^31），这种O(n)时间复杂度的解法会非常慢，导致超时。

快速幂算法（分治思想）

快速幂算法通过分治策略将时间复杂度降低到O(log n)。

算法原理

1. 将指数n分解为二进制表示
2. 利用公式：x^n = x^(n/2) * x^(n/2) （当n为偶数）
3. 对于奇数n：x^n = x * x^((n-1)/2) * x^((n-1)/2)

递归实现

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

迭代实现（更高效）

def myPow(x: float, n: int) -> float:
    def quickMul(N):
        ans = 1.0
        x_contribute = x
        while N > 0:
            if N % 2 == 1:
                ans *= x_contribute
            x_contribute *= x_contribute
            N = N // 2
        return ans
    
    return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)

边界情况处理

实际实现时需要特别注意以下边界情况：

1. n为负数：转换为计算倒数
2. n = -2^31：直接取反会导致整数溢出，需要特殊处理
3. x为0：0的正数次幂为0，0的负数次幂无定义（题目保证不会出现）
4. x为1或-1：可以直接返回结果避免计算

优化后的完整实现：

def myPow(x: float, n: int) -> float:
    if n == 0:
        return 1.0
    if x == 0.0:
        return 0.0
    if x == 1.0:
        return 1.0
    if x == -1.0:
        return 1.0 if n % 2 == 0 else -1.0
    
    res = 1.0
    abs_n = abs(n)
    while abs_n > 0:
        if abs_n % 2 == 1:
            res *= x
        x *= x
        abs_n //= 2
    
    return res if n > 0 else 1.0 / res

复杂度分析

• 时间复杂度：O(log n)，每次迭代都将问题规模减半
• 空间复杂度：O(1)，只使用了常数个额外变量

实际应用中的注意事项

1. 浮点数精度：Python的浮点数实现遵循IEEE 754标准，但连续乘法可能导致精度损失
2. 大数处理：虽然题目限制了输入范围，但在实际工程中需要考虑更大的数值
3. 异常处理：生产代码需要添加对异常输入的处理

扩展思考

1. 模运算下的快速幂：在密码学中常用到大数的模幂运算，可以结合快速幂算法实现

   def pow_mod(x, n, mod):
      res = 1
      while n > 0:
          if n % 2 == 1:
              res = (res * x) % mod
          x = (x * x) % mod
          n = n // 2
      return res
   

2. 矩阵快速幂：该算法可以推广到矩阵幂运算，用于解决斐波那契数列等问题

总结

实现pow(x,n)函数的关键在于： 1. 使用快速幂算法降低时间复杂度 2. 正确处理各种边界情况 3. 根据实际需求选择递归或迭代实现

掌握快速幂算法不仅有助于解决这道LeetCode题目，更是理解分治算法思想的重要案例，在后续学习更复杂的算法时会有广泛应用。 “`