LeetCode 50. Pow(x, n)
8508 ワード
1.タイトルの説明
Implement pow(x, n).
2.問題の解き方
主にいくつかの状況を考慮する必要があり、底数は-1、1、指数は0、正数、負数である.正常な指数が正の場合、このような数学のテクニックを使うことを考えることができます.
res(x,n)={res(x2,n/2)∗xres(x2,n/2)ifn%2==1else
3. code
4.大神解法
4.1 demo1
彼はここで指数が0,正数,負数の場合を特殊に処理した.
4.2 demo2
Implement pow(x, n).
2.問題の解き方
主にいくつかの状況を考慮する必要があり、底数は-1、1、指数は0、正数、負数である.正常な指数が正の場合、このような数学のテクニックを使うことを考えることができます.
res(x,n)={res(x2,n/2)∗xres(x2,n/2)ifn%2==1else
3. code
class Solution {
public:
double myPow(double x, int n) {
if (n == 0)
return 1.0;
if (fabs(x - 1) < 1e-6)
return 1.0;
if (fabs(x + 1) < 1e-6)
return n % 2 ? -1.0 : 1.0;
if (n < 0){
long long tmp = n;
tmp = -tmp;
return _myPow(1 / x, tmp);
}
return _myPow(x, n);
}
double _myPow(double x, long long n) {
if (n == 1)
return x;
if (n % 2){
return x * _myPow(x * x, n >> 1);
}
return _myPow(x * x, n >> 1);
}
};
4.大神解法
4.1 demo1
彼はここで指数が0,正数,負数の場合を特殊に処理した.
public class Solution {
public double pow(double x, int n) {
if(n == 0)
return 1;
if(n<0){
n = -n;
x = 1/x;
}
return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
}
}
4.2 demo2
After reading some good sharing solutions, I'd like to show them together. You can see different ideas in the code.
1. nest myPow
double myPow(double x, int n) {
if(n<0) return 1/x * myPow(1/x, -(n+1));
if(n==0) return 1;
if(n==2) return x*x;
if(n%2==0) return myPow( myPow(x, n/2), 2);
else return x*myPow( myPow(x, n/2), 2);
}
2. double myPow
double myPow(double x, int n) {
if(n==0) return 1;
double t = myPow(x,n/2);
if(n%2) return n<0 ? 1/x*t*t : x*t*t;
else return t*t;
}
3. double x
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0){
n = -n;
x = 1/x;
}
return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}
4. iterative one
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0) {
n = -n;
x = 1/x;
}
double ans = 1;
while(n>0){
if(n&1) ans *= x;
x *= x;
n >>= 1;
}
return ans;
}
5. bit operation
class Solution {
public:
double pow(double x, int n) {
if(n<0){
x = 1.0/x;
n = -n;
}
int unsigned m = n;
double tbl[32] = {0};
double result = 1;
tbl[0] = x;
for(int i=1;i<32;i++){
tbl[i] = tbl[i-1]*tbl[i-1];
}
for(int i=0;i<32;i++){
if( m & (0x1<<i) )
result *= tbl[i];
}
return result;
}
};
If you have other ideas, please leave it below. Thanks.