[leetcode/lintcode 题解] 算法面试真题详解：x的n次幂

描述
实现 pow(x, n). (n是一个整数)
不用担心精度，当答案和标准输出差绝对值小于1e-3时都算正确

在线评测地址：领扣题库官网

样例1
输入: x = 9.88023, n = 3
输出: 964.498

样例2
输入: x = 2.1, n = 3
输出: 9.261

样例3
输入: x = 1, n = 0
输出: 1

注意 n 可能是负数, 需要求一下倒数, 可以在一开始把x转换成倒数, 也可以到最后再把结果转换为倒数.
那么现在我们实现 pow(x, n), n 是正整数的版本:
二分即可: 有xn=xn/2∗xn/2xn=xn/2∗xn/2, 因此可以在 O(logn) 的时间复杂度内实现.
又叫快速幂. 有递归实现和循环实现的版本.
还可以参考一下 fast power 中的二进制的做法。

public class Solution {
    /**
     * @param x the base number
     * @param n the power number
     * @return the result
     */
    public double myPow(double x, int n) {
        boolean isNegative = false;
        if (n < 0) {
            x = 1 / x;
            isNegative = true;
            n = -(n + 1);       // Avoid overflow when n == MIN_VALUE
        }

        double ans = 1, tmp = x;

        while (n != 0) {
            if (n % 2 == 1) {
                ans *= tmp;
            }
            tmp *= tmp;
            n /= 2;
        }
        
        if (isNegative) {
            ans *= x;
        }
        return ans;
    }
}

更多题解参考：九章官网solution