Skip to main content

2-22 50.pow(x, n)

Date：2022-02-27 17:45:52

题目：50.pow(x, n)​

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

示例​

输入: 2.0, 10

输出: 1024.0

分析​

方法有：1.快速幂 + 递归 2.快速幂 + 迭代，这里只采用递归

分治的思想

image-20220222205553485

x * x = x²
x² * x² = x^4
x^4 * x^4 * x = x^9 // 如果为%2的奇数，则补乘一个x，
                                        // 注意计算时候是反过来，所以可以知道%2的值
x^9 * x^9 * x = x^19

详细分析见.https://leetcode-cn.com/problems/powx-n/solution/powx-n-by-leetcode-solution/

题解​

function main() {
  const x = 2
  const n = 10

  const res = myPow(x, n)

  console.log('[res]:', res)
  // [res]: 1024
}
main()

function myPow(x: number, n: number) {
  return n >= 0 ? quickMul(x, n) : 1 / quickMul(x, -n)
}

function quickMul(x: number, n: number) {
  n = Math.floor(n) // 向下取整

  if (n == 0) {
    return 1
  }

  const y = quickMul(x, n / 2)
  return n % 2 == 0 ? y * y : y * y * x
}