50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

暴力法

时间复杂度O(n)

public double myPow(double x, int n) {
        if(n < 0){
            n = -n;
            x = 1/x;
        }
        double result = 1;
        for (int i = 0; i < n; i++) {
            result *= x;
        }
        return result;
    }

分治

    /**
     * 2 分治法：使用递归实现
     * template：
     * 1. terminator
     * 2. process(split your big problems)
     * 3. drill down(subproblems),merge(subresult)
     * 4. reverse states
     */
    /**
     * pow(x,n):
     *  subproblem : subresult = pow(x,n/2)
     *  merge:
     *     if n % 2 = 1 //odd
     *        result = subresult * subresult * x
     *     else //even
     *        result = subresult * subresult
     */

    public double myPow(double x, int n) {
        if (n < 0) {
            n = -n;
            x = 1 / x;
        }
        return fastPow(x, n);
    }

    double fastPow(double x, int n) {
        //1. terminator
        if (n == 0) {
            return 1.0;
        }
        // 2. process(split your big problems)
//        n = n / 2;
        //3. drill down(subproblems),merge(subresult)
        double half = fastPow(x, n / 2);
        return n % 2 == 0 ? half * half : half * half * x;
        // 4. reverse states
    }