Pow(x, n)
Pow(x, n)
本机进度仅保存在当前浏览器
题目描述
实现 pow(x, n)，即计算 x 的整数 n 次幂函数（x 为浮点数，n 为整数，n 可能为负数）。不允许直接调用库函数，时间复杂度要求 O(log |n|)。
示例：x = 2.0，n = 10，输出 1024.0；x = 2.0，n = -2，输出 0.25。
解题思路
- 快速幂：n 为偶数时 x^n = (x * x)^(n/2)；n 为奇数时先分离出一个 x。指数每次减半，共 O(log n) 次乘法。
- 负指数转化为正指数的倒数：x^(-n) = 1 / x^n，注意 n 取绝对值时可能溢出 int 下限（其他语言需转 long）。
- 迭代写法从低位到高位拆 n 的二进制，遇 1 就把当前的平方底数乘进结果，免递归栈。
参考实现
查看参考实现Python · 建议先自行作答
def myPow(x, n):
if n < 0:
x = 1 / x
n = -n
# 迭代快速幂：按 n 的二进制位累乘
ans = 1.0
while n:
if n & 1:
ans *= x
x *= x
n >>= 1
return ans