LeetCode Pow(x, n) 快速冪 Python 實現

題目

實現 pow(x, n)，計算 x 的 n 次冪。n 可為負數。

示例：2^-1 = 0.5，2.1^2 = 4.41。

解題思路：快速冪（二進制分解）

將指數 n 拆解為二進制，利用 x^n = (x^2)^(n/2) 迭代平方。
例：2^8 = ((2^2)^2)^2，只需 3 次乘法，而非 7 次。
算法：

1. 若 n < 0，取 x = 1/x，n = -n。
2. 初始化 res = 1。
3. 當 n > 0：
   • 若 n & 1：res *= x。
   • x *= x，n >>= 1。
4. 返回 res。

Python AC 代碼

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        res = 1.0
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

# 測試
if __name__ == "__main__":
    assert Solution().myPow(2, -1) == 0.5
    assert Solution().myPow(2.1, 2) == 4.41

複雜度

• 時間：O(log n)，每次循環指數減半。
• 空間：O(1)。

注意點

• Python 整數無溢出風險，C++ 需用 long long 存儲 n 避免 INT_MIN 取絕對值溢出。
• 浮點數精度誤差屬正常，OJ 通常允許 1e-5 相對誤差。