Pow(x, n)

LeetCode #50

Description:

Implement pow(x, n).

Example:

Note

Idea:

典型的DC思想，不过不知道为啥，有种解法leetCode超时。

Code:

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;

        double half=myPow(x, n/2);

        if(n%2==0) return half*half;
        else return n<0? half*half*1/x : half*half*x;   
    } 
};

这样的话超时：

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        if(n<0){
           return 1.0/myPow(x, -1*n);
        }

        double half=myPow(x, n/2);

        if(n%2==0) return half*half;
        else return half*half*x;   
    }

};