题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方
思路：
1）判断输入的数是否正确
底=0且指数小于0
2）判断指数是否为负
3）由指数的大小确定累乘的次数
问题是效率不高，时间复杂度O（n）
解法1：
逐个乘
class Solution {
bool invalidInput=false; //返回错误方式
public:
double Power(double base, int exponent)
{
if(equal(base,0.0)&&exponent<0)//如果指数小于0且底数为0时
{
invalidInput=true;
return 0.0;
}
int absexponent=exponent;
if(exponent<0)
absexponent=-exponent;
double res=getPower(base,absexponent);//调用子函数
if(exponent<0)
res=1.0/res;
return res;
}
public:
bool equal(double num1,double num2)//判断一个浮点数是否为0
{
if(num1-num2>-0.000001&&num1-num2<0.000001)
return true;
else
return false;
}
public:
double getPower(double b,int e)
{
double result=1;
for(int i=1;i<=e;i++)
{
result*=b;
}
return result;
}
};
解法2：
使用公式
时间复杂度O（logn）
class Solution {
bool invalidInput=false; //返回错误方式
public:
double Power(double base, int exponent)
{
if(equal(base,0.0)&&exponent<0)//如果指数小于0且底数为0时
{
invalidInput=true;
return 0.0;
}
int absexponent=exponent;
if(exponent<0)
absexponent=-exponent;
double res=getPower(base,absexponent);//调用子函数
if(exponent<0)
res=1.0/res;
return res;
}
public:
bool equal(double num1,double num2)//判断一个浮点数是否为0
{
if(num1-num2>-0.000001&&num1-num2<0.000001)
return true;
else
return false;
}
public:
double getPower(double b,int e)
{
if(e==0)
return 1.0;
if(e==1)//递归结束条件
return b;
double result=getPower(b,e>>1);//每次右移
result*=result;
if((e&1)==1)//关键，区分指数是偶数或者是奇数的关键 在栈中参数调用时返回
result*=b;
return result;
}
};
调用过程举例：
