Question

面试题 16. 数值的整数次方

题目描述

实现 pow(_x_, _n_) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

 

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

 

提示：

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

 

注意：本题与主站 50 题相同：https://leetcode.cn/problems/powx-n/

解法

方法一：数学（快速幂）

快速幂算法的核心思想是将幂指数 $n$ 拆分为若干个二进制位上的 $1$ 的和，然后将 $x$ 的 $n$ 次幂转化为 $x$ 的若干个幂的乘积。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为幂指数。

class Solution:
  def myPow(self, x: float, n: int) -> float:
    def qpow(a: float, n: int) -> float:
      ans = 1
      while n:
        if n & 1:
          ans *= a
        a *= a
        n >>= 1
      return ans

    return qpow(x, n) if n >= 0 else 1 / qpow(x, -n)

class Solution {
  public double myPow(double x, int n) {
    return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long) n);
  }

  private double qpow(double a, long n) {
    double ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a;
      }
      a = a * a;
    }
    return ans;
  }
}

class Solution {
public:
  double myPow(double x, int n) {
    auto qpow = [](double a, long long n) {
      double ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans *= a;
        }
        a *= a;
      }
      return ans;
    };
    return n >= 0 ? qpow(x, n) : 1 / qpow(x, -(long long) n);
  }
};

func myPow(x float64, n int) float64 {
  qpow := func(a float64, n int) float64 {
    ans := 1.0
    for ; n > 0; n >>= 1 {
      if n&1 == 1 {
        ans *= a
      }
      a *= a
    }
    return ans
  }
  if n >= 0 {
    return qpow(x, n)
  }
  return 1 / qpow(x, -n)
}

function myPow(x: number, n: number): number {
  const qpow = (a: number, n: number): number => {
    let ans = 1;
    for (; n; n >>>= 1) {
      if (n & 1) {
        ans *= a;
      }
      a *= a;
    }
    return ans;
  };
  return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
}

impl Solution {
  #[allow(dead_code)]
  pub fn my_pow(x: f64, n: i32) -> f64 {
    let mut x = x;
    let n = n as i64;
    if n >= 0 {
      Self::quick_pow(&mut x, n)
    } else {
      1.0 / Self::quick_pow(&mut x, -n)
    }
  }

  #[allow(dead_code)]
  fn quick_pow(x: &mut f64, mut n: i64) -> f64 {
    // `n` should greater or equal to zero
    let mut ret = 1.0;
    while n != 0 {
      if (n & 0x1) == 1 {
        ret *= *x;
      }
      *x *= *x;
      n >>= 1;
    }
    ret
  }
}

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function (x, n) {
  const qpow = (a, n) => {
    let ans = 1;
    for (; n; n >>>= 1) {
      if (n & 1) {
        ans *= a;
      }
      a *= a;
    }
    return ans;
  };
  return n >= 0 ? qpow(x, n) : 1 / qpow(x, -n);
};

public class Solution {
  public double MyPow(double x, int n) {
    return n >= 0 ? qpow(x, n) : 1.0 / qpow(x, -(long)n);
  }

  private double qpow(double a, long n) {
    double ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans *= a;
      }
      a *= a;
    }
    return ans;
  }
}