50. Pow(x, n)
Implement pow(x, n).
根据经验，题干越简单的题目，坑越多。
题目要求我们实现一个计算pow()函数，这个函数是用来计算乘方的。题目中没有给出n的范围，我们姑且按照实数范围对其进行考虑。
- 当n>0时，不断让x相乘即可，注意你的结果最好使用
long long int,以防溢出 - n==0时，若x不为0，返回1即可
- n<0时，让x的倒数不断相乘
于是第一版代码在经过修改之后通过了，因为是数值计算题，会涉及很多的corner case,代码中有很多if语句来对边界条件进行判断，代码如下:
/*solution1 20ms*/
class Solution {
public:
double myPow(double x, int n) {
if(x&&!n)
return 1;
double res=1,flag=0;
if(x==-1.0)
return n&1==0||n==INT_MIN? 1:-1;
if(n<0){
if(n==INT_MIN&&x!=1)/*When n==INT_MIN,if you use abs() ,
will cause overflow,for the abstract of INT_MIN is larger than INT_MAX for 1*/
return 0;
for(int i=0;i<abs(n);i++){
flag=res;
res=res*(1/x);
if(res==flag)/*flag is used to prevent from time limit exceed，
for n may be very large, when res is going to be zero,
the iteration will be useless*/
return res;
}
}
else{
for(int i=0;i<n;i++){
flag=res;
res=res*x;
if(res==flag)
return res;
}
}
return res;
}
};
正是由于一大堆的条件判断，这个算法很慢。因此，在参考了讨论区之后，我发现了用二分法解决这个问题。
要求x^n,可以求x^(n/2)*x^(n/2),于是，我们就有了用二分法解决问题的思路,代码如下:
class Solution {
private:
double power(double x,int n){
if(x&&!n)
return 1;
double res=power(x,n/2);
if(n%2==0)
return res*res;
else
return res*res*x;
}
public:
double myPow(double x, int n) {
if(n<0)
return 1/power(x,-n);
else
return power(x,n);
}
};