50. Pow(x,n)

1. 题目描述

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

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

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

提示：

• -100.0 < x < 100.0
• -2<= n <= 2-1
• -10 <= xn <= 10

  2. 解题思路

这道题直接的思路就是暴力计算，判断n的正负，如果为正就让底数x直接累乘，如果为负就让底数的倒数1/x累乘。

但是超出了时间限制，可以使用二分法进行优化：**

我们可以进行折半计算，每次将n缩小一半，通过递归最终获得结果。注意，当n为奇数时，需要多乘一次x的值。

时间复杂度：O(logn)，空间复杂度：O(logn)

3. 代码实现

暴力：

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(n === 0){
        return 1
    }
    const base = n > 0 ? x : 1/x
    let result = 1
    for(let i = 1; i <= Math.abs(n); i++){
        result = result * base
    }
    return result
};

二分法：

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if(n === 0){
        return 1
    }else if(n === 1){
        return x
    }else if(n === -1){
        return 1/x
    }
    const base = n > 0 ? x : 1/x
    const half = parseInt(n/2, 10)
    let result = myPow(x, half)
    if(n % 2){
        return base * result * result
    }
    return result * result
};

4. 提交结果

二分法：