50. Pow(x, n)

Implement pow(x, n).

Hide Company Tags LinkedIn Google Bloomberg Facebook Hide Tags Binary Search Math Hide Similar Problems (E) Sqrt(x) (M) Super Pow

** 解题思路 **
这道题有几种解题思路。主要思想是用二分查找来做，需要区分n < 0, n %2 == 1 or n % 2 == 0 几种情况。例如，

1
2
2 ^ 5  = 2 * myPow( 2 * 2 , 5/2)  
2 ^ 4 =  myPow(2 * 2 ,  4/ 2)

当然如果用暴力做法 return x * x * x … * x (n 个x 相乘）会造成leetcode oj报错。下面是五种写法，仅供参考。

5 solutions for pow(x, n)

nest myPow

1
2
3
4
5
6
7
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);
}

double myPow

1
2
3
4
5
6
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;
}

double x

1
2
3
4
5
6
7
8
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);
}

iterative one

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

bit operation see this solution If you have other ideas, please leave it below. Thanks.

文章目录