50. Pow(x, n)
题目描述
实现函数 pow(x, n)：输入浮点数 x 和整数 n，返回 x 的 n 次方 x^n。
n 可以是负数或 0。n 为负时，x^n 等于 1 / x^(-n)。
输入：x = 2.0, n = 10 输出：1024.00000
解释：2^10 = 1024。
输入：x = 2.1, n = 3 输出：9.26100
解释：2.1^3 = 9.261。判题时与答案相差不超过 10^-5 即视为正确。
输入：x = 2.0, n = -2 输出：0.25000
解释：2^-2 = 1/2^2 = 1/4 = 0.25。
数据范围
-100.0 < x < 100.0-2^31 <= n <= 2^31 - 1n是整数。x不为 0，或者n > 0。-10^4 <= x^n <= 10^4
解题思路：迭代快速幂（二进制拆分）
快速幂：把 n 写成二进制，x^n 就是若干个 x^(2^k) 的乘积。从低位到高位扫描 n 的二进制：用 x 保存当前的 x^(2^k)，每轮平方一次；如果当前位是 1，就把它乘进答案。n 为负数时先把 x 换成 1/x、n 取反。
为什么正确
每轮开始时，ans * x^n 等于最终答案；右移 n 并平方 x 不改变这个乘积。
复杂度分析
时间 O(log|n|)，空间 O(1)。
易错点
n = -2^31 时在 C++/Java 里直接取反会溢出，要先转成 64 位整数。用逐次相乘的 O(n) 做法在 n 约 2^31 时会超时。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x, n = 1 / x, -n
ans = 1.0
while n:
if n & 1:
ans *= x
x *= x
n >>= 1
return ansclass Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1.0;
while (N != 0) {
if ((N & 1) == 1) {
ans *= x;
}
x *= x;
N >>= 1;
}
return ans;
}
}class Solution {
public:
double myPow(double x, int n) {
long long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1.0;
while (N) {
if (N & 1) {
ans *= x;
}
x *= x;
N >>= 1;
}
return ans;
}
};func myPow(x float64, n int) float64 {
if n < 0 {
x, n = 1/x, -n
}
ans := 1.0
for n != 0 {
if n&1 == 1 {
ans *= x
}
x *= x
n >>= 1
}
return ans
}var myPow = function(x, n) {
if (n < 0) {
x = 1 / x;
n = -n;
}
let ans = 1.0;
while (n) {
if (n % 2 === 1) {
ans *= x;
}
x *= x;
n = Math.floor(n / 2);
}
return ans;
};function myPow(x: number, n: number): number {
if (n < 0) {
x = 1 / x;
n = -n;
}
let ans = 1.0;
while (n) {
if (n % 2 === 1) {
ans *= x;
}
x *= x;
n = Math.floor(n / 2);
}
return ans;
}其他解法
两者都是 O(log n) 次乘法：递归版按 n 折半自顶向下分治，直观但占用递归栈；迭代版按 n 的二进制位自底向上累乘，空间 O(1)。
解法 2：递归快速幂（分治） 时间 O(log n)，空间 O(log n)
利用 x^k = (x^(k/2))^2（k 为偶数）或 (x^(k/2))^2 · x（k 为奇数），先递归求出 x^(k/2)，再平方并按奇偶决定是否多乘一个 x。递归到 k=0 时返回 1。n 为负数时先求 x^(-n) 再取倒数，C++/Java 用 64 位整数避免 -2^31 取反溢出。
分治思路自顶向下，最容易从数学公式直接推出，便于理解快速幂为什么是对数级。代价是 O(log n) 的递归栈；迭代版从 n 的二进制位自底向上累乘，省去栈空间。
class Solution:
def myPow(self, x: float, n: int) -> float:
def quick(k):
if k == 0:
return 1.0
half = quick(k // 2)
return half * half if k % 2 == 0 else half * half * x
return quick(n) if n >= 0 else 1.0 / quick(-n)class Solution {
double quick(double x, long k) {
if (k == 0) return 1.0;
double half = quick(x, k / 2);
return k % 2 == 0 ? half * half : half * half * x;
}
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quick(x, N) : 1.0 / quick(x, -N);
}
}class Solution {
public:
double quick(double x, long long k) {
if (k == 0) return 1.0;
double half = quick(x, k / 2);
return k % 2 == 0 ? half * half : half * half * x;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quick(x, N) : 1.0 / quick(x, -N);
}
};func myPow(x float64, n int) float64 {
var quick func(k int) float64
quick = func(k int) float64 {
if k == 0 {
return 1.0
}
half := quick(k / 2)
if k%2 == 0 {
return half * half
}
return half * half * x
}
if n >= 0 {
return quick(n)
}
return 1.0 / quick(-n)
}var myPow = function(x, n) {
const quick = (k) => {
if (k === 0) return 1.0;
const half = quick(Math.floor(k / 2));
return k % 2 === 0 ? half * half : half * half * x;
};
return n >= 0 ? quick(n) : 1.0 / quick(-n);
};function myPow(x: number, n: number): number {
const quick = (k: number): number => {
if (k === 0) return 1.0;
const half = quick(Math.floor(k / 2));
return k % 2 === 0 ? half * half : half * half * x;
};
return n >= 0 ? quick(n) : 1.0 / quick(-n);
}