50. Pow(x, n)

发表评论
349 views

 ›
50. Pow(x, n)

官方链接

https://leetcode-cn.com/problems/powx-n/

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

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

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

说明:

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

解法一

暴力

result = 1
for i:0 -> n {
  result *=x
}
O(n)

leetcode 执行暴力法代码 超出时间限制

class Solution:
    def myPow(self, x: float, n: int) -> float:
      if n < 0:
        x = 1 / x
        n = -n
      result = 1
      for i in range(1, n+1):
        result = result * x
      return result

解法二

分治递归

templage

  1. terminator
  2. process(split your big problem)
  3. drill down subproblems merge(sub result)
  4. reverse states

x 为奇数直接除以 2 会丢掉一个 2，所以需要在乘一个

x^n ---> 2^10:  2^5 -> (2^2)*2
pow(x, n):
  subproblem: subresult = pow(x, n/2)

merge:
  if n % 2 == 1 {
    // odd
    result = subresult * subresult * x
  } else {
    result = subresult * subresult
  }

O(log(n))
class Solution:
    def myPow(self, x: float, n: int) -> float:
      if n < 0:
        x = 1 / x
        n = -n
      return self.fastPow(x, n)

    def fastPow(self, x, n):
      if n == 0:
        return 1.0
      half = self.fastPow(x, n // 2)
      if n % 2 == 0:
        return half * half
      else:
        return half * half * x

class Solution {
    public double myPow(double x, int n) {
        return helper(x, (long)n);
    }

    public double helper (double x, long n) {
        if (n == 0) return 1;
        if (n < 0) return 1.0 / helper(x, -n);

        double half = helper(x, n / 2);
        if (n % 2 == 0) return half * half;
        else return half * half * x;
    }
}

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if not n:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2:
            return x * self.myPow(x, n - 1)
        return self.myPow(x*x, n/2)

解法三

位运算 非递归

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n
        pow = 1
        while n:
            if n & 1:
                pow *= x
            x *= x
            n >>= 1
        return pow

解法四

快速幂

参考链接

class Solution {
    public double myPow(double x, int n) {
        return helper(x, (long)n);
    }

    public double helper (double x, long n) {

        if (n < 0) {
            x = 1.0 / x;
            n = -n;
        }

        // 幂结果是在变化过程中所有当指数为奇数时底数的乘积
        double result = 1.0;
        while (n > 0) {
            if (n % 2 != 0) {
                // 如果指数为奇数, 把指数减去1, 使其变成一个偶数
                result = result * x;
            }
            // 指数为偶数, 底数变为原来的平方, 指数缩小为原来的一半
            x = x * x;
            n /= 2;
        }
        return result;
    }
}

解法五

牛顿迭代法