分治算法：

从右往左开始递归计算，假设y=x^(n/2)，那么当n为偶数时，x^n=y*y，当n为奇数时，x^n=y*y*x。

另外，注意n有可能是负数。

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