JAVA 牛牛

50. Pow(x, n)

  • May 11, 2020
  • 0 views
  • 难度：中等
  • 本题涉及算法： 递归 折半计算
  • 思路： 递归 折半计算
  • 类似题型:

50. Pow(x, 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] 。

方法一 暴力

解题思路 时间会超时

  • 先对 n 的正负做判断
  • 当 n 为正数 $x^n$
  • 当 n 为负数 $(1/x)^n$

    java

    class Solution {
  public double myPow(double x, int n) {
      double a = 1.0;
      if(n<0) {
          x = 1/x;
          n = -n;
      }
      for(int i = 0;i<n;i++) {
          a *=x;
      }
      return a;
  }
}

方法二 改良暴力

  • 通过折半计算，每次把 n 减半，降低空间复杂度

    java

    class Solution {
  public double myPow(double x, int n) {
      double a = 1.0;
      if(n<0) {
          x = 1/x;
          n = -n;
      }
      for(int i = n;i != 0;i /= 2) {
          if (i % 2 != 0)
              a *= x;
          x *=x;
      }
      return a;
  }
}

python

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        res = 1;
        if n == 0:
            return 1
        if n < 0:
            x = 1 / x
            n = -n
        while n:
            if n % 2 == 0:
                x *= x
                n /= 2
            else:
                res *=x
                n -= 1
        return res

方法三 递归

解题思路

主要是注意n的正负，这个题比较简单了，直接递归调用就行。

如果 n 是负数，那么相当于求 (1/x)^(-n)。 如果 n 是正数 且 奇数，那么结果需要单独乘以 x 如果 n 是正数 且 偶数，求 (x^2)^(n/2)，一直递归下去即可。 时间复杂度是 $O(1)$，空间复杂度是 $O(1)$。 我认为这个代码是 $O(1)$，因为n只有32位，循环次数是有上限的常数

代码

class Solution {
    public double myPow(double x, int n) {
        if(n==0)
            return 1;
        if(n<0) {
            x = 1/x;
            n = -n;
        }
        if (n%2!=0)
            return x * myPow(x,n-1);
        return myPow(x*x,n/2);
    }
}

python

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n < 0:
            x = 1 / x
            n = -n
        if n % 2:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n / 2)

快速幂

计算 $x^ n$ 通常需要 $n$ 次乘法, 时间复杂度为 $O(n)$ , 当 $n$ 非常大的时候, 运算效率很低.

快速幂是通过把 $n$ 转化为二进制来实现的. 例如: 计算 $x^{14}$, 14 可以用二进制表示为:

$14 = (1110)_ 2 = 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0 $

那么对应的乘法可以表示为:

$x^{14} = x^{2 ^3} * x^{2^2} * x^{2 ^1} $

转换后乘法运算次数减少, 每次计算 $x^{2^n}$, 再决定是否将这个数字加入到最终结果里面去. 代码如下:

python

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

java

class Solution {
    public double myPow(double x, int n) {
        double res = 1.0;
        long b = n; // 防止 int 溢出， 使用 long
        if(b<0) {
            x = 1/x;
            b = -b;
        }
        while (b >0) {
            if ((b&1) ==1)
                res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }
}
Search