leetcode 实现乘方 - pow(x,y)

leetcode（java实现）

问题描述：

50.pow(x,y)
Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:Input: 2.10000, 3

Output: 9.26100

Example 3:Input: 2.00000, -2

Output: 0.25000
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]

问题分析：

• 【思路1-Java】递归实现

  采用递归实现，那么本题的终止条件是 n == 0 和 n == 1。这里不采用下面的做法,因为时间复杂度为 O(n)，加上题目的限制会超时。
  public class Solution {
  public double myPow(double x, int n) {
  if(n == 0) return 1;
  if(n == 1) return x;
  return myPow(x, n-1) * x;
  }
  }
  另外，本题的难点主要是在边界条件：如果 n < 0，是不是 n = -n， x = 1 / x ，再进行递归就能解决了呢？如果 n = Intege.MIN_VALUE，n = -n 会出现溢出，怎么办呢？我们可以先将 n / 2 赋值给 t，再将 t = -n，就不会出现溢出问题。

• 【思路2-Java】非递归实现

  m^n的理解：加入 n = 13，13在二进制中表示为：00001101，那么13 = 2^3 + 2^2 + 2^0。

算法实现：

略

参考代码：

用方法二来实现

class Solution {
    public double myPow(double x, int n) {
        int exp = n<0 ? -n-1 : n;   //边界和负值处理
        double product = 1;     //记录结果
        for (double tmp = x; exp > 0; exp>>=1)
        {
            if ((exp&1) != 0)
                product *= tmp;     //如果二进制位为1，则计算
            tmp *= tmp;     //记录中间结果
        }
        return n<0 ? 1/product/x : product;     //正负及边界处理
    }
}