剑指offer - 数值的整次方(四种解法) - JavaScript

题目描述:给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的 exponent 次方。

保证 base 和 exponent 不同时为 0

题目描述

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

解法 1: 内置函数

第一反应直接调用库函数。

// ac地址:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
// 原文地址:https://xxoo521.com/2019-12-31-pow/

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    return Math.pow(x, n);
};

解法 2: 二分法

为了方便讨论,假设指数exponent是正数。那么递归式如下:

  • 如果exponent是偶数,Power(base, exponent) = Power(base, exponent / 2) * Power(base, exponent / 2)
  • 如果exponent是奇数,Power(base, exponent) = base * Power(base, exponent / 2) * Power(base, exponent / 2)

对于负指数exponent的情况,取其绝对值先计算。将最后结果取倒数即可。

时间复杂度是 O(logN);由于采用递归结构,空间复杂度是 O(logN)。

// ac地址:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
// 原文地址:https://xxoo521.com/2019-12-31-pow/

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    const isNegative = n < 0; // 是否是负指数
    const result = absMyPow(x, Math.abs(n));
    return isNegative ? 1 / result : result;
};

function absMyPow(base, exponent) {
    if (exponent === 0) {
        return 1;
    }

    if (exponent === 1) {
        return base;
    }

    const subResult = absMyPow(base, Math.floor(exponent / 2));
    return exponent % 2 ? subResult * subResult * base : subResult * subResult;
}

解法 3: 位运算

第 2 种解法可以转换为迭代写法。迭代写法和位运算有关。

为了理解,假设 base=3,exponent= 5。那么 5 的二进制是:101。所以,3 的 5 次方可以写成下图的格式:

可以看到,对 base 进行自乘,导致 base 的指数每次都扩大 2 倍。与 exponent 的二进制相对应。

以上图为例,整个算法的流程如下:

  • 结果值 result 初始为 1
  • base 初始为 3,此时 exponent 的二进制最右位为 1,更新结果为:base * result
  • exponent 右移一位。base 进行累乘,base 更新为 3 的 2 次方。由于 exponent 的二进制最右位为 0,不更新结果
  • exponent 右移一位。base 进行累乘,base 更新为 3 的 4 次方。此时 exponent 的二进制最右位为 1,更新结果为:base * result
  • 结束

代码如下:

// ac地址:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
// 原文地址:https://xxoo521.com/2019-12-31-pow/

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    if (n === 0) {
        return 1;
    }
    if (n === 1) {
        return x;
    }

    const isNegative = n < 0; // 是否是负指数
    let absn = Math.abs(n);
    let result = 1;
    while (absn) {
        // 如果n最右位是1,将当前x累乘到result
        if (absn & 1) {
            result = result * x;
        }

        x = x * x; // x自乘法
        absn = Math.floor(absn / 2); // n右移1位
    }

    return isNegative ? 1 / result : result;
};

更多资料

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×