实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数
方法1:比较普通的做法，明显面试官不是想看这个
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
for (long i = 0; i < N; i++)
ans = ans * x;
return ans;
}
}
注意：
这里为什么需要使用long 来先保存n，int的范围是-2147483648~2147483647，因为如果n是负数，int的负数边界，进行幂运算会变为正2147483648，此时已经超过了int的正边界2147483647
复杂度分析
时间复杂度：O(n). 我们需要将 x 连乘 n 次。
空间复杂度：O(1). 我们只需要一个变量来保存最终 x 的连乘结果。
方法2:使用递归，进行对半操作
class Solution {
public double myPow(double x, int n) {
long N = n;
if(n==0){
return 1.0;
}
if(N<0){
x=1/x;
N=-N;
}
return quick(x,N);
}
public double quick(double x,long n){
if(n==1){
return x;
}
double half = quick(x,n/2);
long res = n%2;
if(n%2==0){
return half*half;
}else {
return half*half*x;
}
}
}