利用二进制的思想，我喜欢称其为倍增思想。
实现把x 的 x， x^2 , x^4 , x^8, x^16，x^32 ....算出来
存在数组里：
pow[0] = x;
pow[1] = x^2;
pow[2] = x^4;
pow[3] = x^8;
....
有了这个数组，任意的 x^n 都可以表示成 x * x^n1 * x^n2....
比如 x^15 = x^8 + x^4 + x^2 +x;
所有任意的x^n 都可以用log(n)的效率完成
class Solution {
public:
double pow[35];
double myPow(double x, int n) {
if(n==0)
return 1;
long long int n2;
int tag=0;
if(n<0){
n2 = (long long int)n*-1;
tag=1;
}
else
n2=n;
long long int pos = 1;
int i=0;
double ans = x;
pow[i]=ans;
while((pos<<1)<=n2 && (pos<<1)>0)
{
ans*=ans;
pos <<= 1;
i++;
pow[i]=ans;
}
ans=1;
while(n2)
{
if(n2<pos)
{
pos>>=1;
i--;
continue;
}
n2-=pos;
ans*=pow[i];
pos>>=1;
i--;
}
if(tag==1)
return 1.0/ans;
else
return ans;
}
};内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
