Skip to content

LeetCode题解:50. Pow(x, n),迭代分治,JavaScript,详细注释 #201

@chencl1986

Description

@chencl1986

原题链接:https://leetcode-cn.com/problems/powx-n/

解题思路:

  1. x的n次幂可以分解为x的n/2次幂的平方。
  2. 按照步骤1的思路,通过递归逐级分解,时间复杂度即为O(logn)。
  3. 如果n为负,问题可以转换为计算1除以x的n次幂。
  4. 对于代码中powerresultsubResult的关系,可以参考官方题解50. Pow(x, n) (快速幂,清晰图解)。为了方便理解,我以myPow(2, 10)为例,列出每次循环的结果。表格中power的值表示每次进入循环时的值,而非循环结束时的值,具体可以参考console.log打印的位置。
power subResult result
10 x^2 1
5 x^4 x^2
2 x^8 x^2
1 x^16 x^10
/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  let result = 1; // 存储最终结果
  let power = Math.abs(n); // 计算n次幂,n为负时转换为正数再计算
  let subResult = x; // 存储中间结果的平方

  while (power > 0) {
    console.log(power)
    // 如果power为奇数,则将中间结果加入到最终结果
    if (power % 2) {
      result *= subResult;
    }
    // 每次迭代都计算总监接过的平方
    subResult = subResult * subResult;
    // 每次迭代都将power减半,同时处理小鼠问题
    power = Math.floor(power / 2);
    console.log(subResult, result)
  }

  // n为正数直接返回结果,为负数则返回1/result
  return n > 0 ? result : 1 / result;
};

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions