16. 数值的整数次方

来源

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

题目

实现函数 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/2 = 1/4 = 0.25

说明

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

思路 1

分治法
n 为偶数时 Pow(x, n) = Pow(x, n / 2) * Pow(x, n / 2)
n 为奇数时 Pow(x, n) = x * Pow(x, (n - 1) / 2) * Pow(x, (n - 1) / 2)
使用递归

解题 1

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

  if (n < 0) {
    return 1 / myPow(x, -n);
  }

  const odd = n & 1;
  const res = myPow(x, n >> 1);
  return (odd ? x : 1) * res * res;
};

思路 2

同理可以使用循环实现

解题 2

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

  let res = 1;
  let negative = n < 0;

  if (negative) n = -n;

  while (n > 0) {
    if (n & 1) {
      res *= x;
    }
    x *= x;
    n >>= 1;
  }

  if (negative) return 1 / res;

  return res;
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch