剑指 Offer 16. 数值的整数次方

题目描述

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 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

说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

用快速幂方法，递归二分，让时间复杂度在 ，不然 会超时。
快速幂原理就是 ，针对 32 位最大数，二分下来就是最多 32 次。
用递归就容易理解了。

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (x === 0) return '0.00000';
    if (n === 0) return '1.00000';
    if (n < 0) {
        x = 1 / x;
        n *= -1;
    }
    let mod = n % 2;
    let div = Math.floor(n / 2);
    let mul = myPow(x, div);
    return (mod > 0 ? x : 1) * mul * mul;
};