1、前言

2、思路

这道题的基本思路是，幂分为小于0和大于等于0的。如果小于0，如3^-2=1/9；大于等于0比较简单。

那么如果幂是偶数，如 3^4 = 81，则可以分为 3^2 * 3^2 = 81，每次将幂二等分，最后再合并起来。
如果为奇数，则在此基础上再乘一个数，如 3^5 = 3^2 * 3^2 * 3

3、代码

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

    private double divideAndConquer(double x, int n) {
        if (n == 0) {
            return 1;
        }

        if (x == 1) {
            return 1;
        }

        // 分治思想：分
        double square = divideAndConquer(x, n / 2);
        // 分治思想：合，分为奇数偶数
        return n % 2 == 0 ? square * square : square * square * x;
    }

}