LeetCode 50. Pow(x, n)

Implement pow(x, n).
Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100

解析：
通过递归法，采用分治的思想，根据公式如果n是偶数\(x^{2n}=x^{n}x^{n}\)，如果n是奇数，则有\(x^{2n+1}=x^n*x^n*x\)
通过递归推导，我们不必将x相乘n次，只需要logN次就可以了。
时间 O(logN) 空间 O(logN)

具体代码如下：

class Solution {
public:
    double myPow(double x, int n) {
        if (n==0) return 1;
        if (n==1) return x;
        if (n==-1) return 1/x;
        return myPow(x*x,n/2)*(n%2==0?1:n>0?x:1/x);
    }
};

执行效果

非递归版本

class Solution {
public:
    double myPow(double x, int n) {
        double result = 1;
        unsigned long long p;
        if(n < 0)
        {
            long long temp = n;
            p = -temp;
            x = 1/x;
        }else
            p = n;
        while(p)
        {
            if(p%2==1)
                result *= x;
            x *=x;
            p/=2;
        }
        return result;
    }
};