题干：实现 pow(x, n) ，即计算 x 的 n 次幂函数。
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。
来源：力扣（LeetCode）
链接
语言：Java
题目分析：
1：输入的边界 -100.0 < x < 100.0，-2,147,483,648< n <2,147,483,647；double双浮点数10^-308~10^308和-10^-308~-10^308
2：输出的边界 100^2147483647 目前没有特别好的数据类型可以覆盖，暂不考虑。
x!=0,n=0, return 1; x=0, n=0 时怎么办？
3：n次幂函数 ，既为n次x相乘，最简单的解法O(n)
解法分析：n < 0 就是 1/x^(-n), 当n = -2,147,483,648，需要对n特殊处理。
解法一：进行二分法拆解，x^n = x^(n/2) * x^(n/2)；x^(n/2) = x^(n/4) * x^(n/4)，边界为n/4=1；
class Solution {
public double myPow(double x, int n {
if (x == 0.0) return 0.0;
if (n == 0) return 1.0;
long nn = n;
return n > 0 ? quickMul(x , nn) : 1 / quickMul(x, -nn);
}
private double quickMul(double x, long n) {
if (n == 0) return 1.0;
double ansTemp = quickMul(x, n / 2);
return n % 2 == 0 ? ansTemp * ansTemp : ansTemp * ansTemp * x;
}
}
解法二：对n转码为二进制，比如9 = 1001，ans = x^(2^0) * x^(2^3);
class Solution {
public double myPow(double x, int n {
if (x == 0.0) return 0.0;
if (n == 0) return 1.0;
long nn = n;
return n > 0 ? quickMul(x , nn) : 1 / quickMul(x, -nn);
}
private double quickMul(double x, long n) {
double x_temp = x;
double ans = 1.0;
while (n != 0) {
if (n % 2 == 1) {
ans *= x_temp;
}
n /= 2;
x_temp *= x_temp;
}
return ans;
}
}
需要注意的坑：
1：x = 0.0
2：n = 0
3：n = -2,147,483,648 int -n 会变成0 ！！！！
