题目

mplement pow(x, n), which calculates x raised to the power n (0050. Pow(x, n) (M) - 图1).

Example 1:

  1. Input: 2.00000, 10
  2. Output: 1024.00000

Example 2:

  1. Input: 2.10000, 3
  2. Output: 9.26100

Example 3:

  1. Input: 2.00000, -2
  2. Output: 0.25000
  3. Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range $[−2^{31}, 2^{31} − 1]$

题意

手动实现乘方运算。

思路

方法参考快速幂(二分幂)。

代码实现

Java

递归

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         if (Double.compare(x, 1.0) == 0) {
  4.             return 1.0;
  5.         }
  7.         double pow = binaryPow(x, n);
  8.         return n < 0 ? 1 / pow : pow;
  9.     }
  11.     private double binaryPow(double x, int n) {
  12.         if (n == 0) {
  13.             return 1;
  14.         }
  16.         double temp = binaryPow(x, n / 2);
  17.         return n % 2 == 0 ? temp * temp : temp * temp * x;
  18.     }
  19. }

迭代

  1. class Solution {
  2.     public double myPow(double x, int n) {
  3.         if (Double.compare(x, 1.0) == 0) {
  4.             return 1.0;
  5.         }
  7.         double pow = 1.0;
  8.         // 无论正数负数，除以2相当于将其绝对值的二进制右移一位
  9.         for (int i = n; i != 0; i /= 2) {
  10.             // 无论正数负数，不是偶数说明其绝对值二进制末位为1
  11.             if (i % 2 != 0) {
  12.                 pow *= x;
  13.             }
  14.             x *= x;
  15.         }
  17.         return n < 0 ? 1 / pow : pow;
  18.     }
  19. }

JavaScript

递归

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

  let pow = myPow(x, Math.trunc(n / 2))
  if (n % 2 === 0) {
    return pow * pow
  } else if (n > 0) {
    return pow * pow * x
  } else {
    return (pow * pow) / x
  }
}

迭代

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  let pow = 1
  let isMinus = n < 0
  while (n !== 0) {
    if (n % 2 !== 0) {
      pow *= x
    }
    x *= x
    n = Math.trunc(n / 2)
  }
  return isMinus ? 1 / pow : pow
}