leetcode（java實(shí)現(xiàn)）

問題描述：

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】遞歸實(shí)現(xiàn)

  采用遞歸實(shí)現(xiàn)，那么本題的終止條件是 n == 0 和 n == 1。這里不采用下面的做法,因?yàn)闀r(shí)間復(fù)雜度為 O(n)，加上題目的限制會(huì)超時(shí)。
  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;
  }
  }
  另外，本題的難點(diǎn)主要是在邊界條件：如果 n < 0，是不是 n = -n， x = 1 / x ，再進(jìn)行遞歸就能解決了呢？如果 n = Intege.MIN_VALUE，n = -n 會(huì)出現(xiàn)溢出，怎么辦呢？我們可以先將 n / 2 賦值給 t，再將 t = -n，就不會(huì)出現(xiàn)溢出問題。

• 【思路2-Java】非遞歸實(shí)現(xiàn)

  m^n的理解：加入 n = 13，13在二進(jìn)制中表示為：00001101，那么13 = 2^3 + 2^2 + 2^0。

算法實(shí)現(xiàn)：

略

參考代碼：

用方法二來實(shí)現(xiàn)

class Solution {
    public double myPow(double x, int n) {
        int exp = n<0 ? -n-1 : n;   //邊界和負(fù)值處理
        double product = 1;     //記錄結(jié)果
        for (double tmp = x; exp > 0; exp>>=1)
        {
            if ((exp&1) != 0)
                product *= tmp;     //如果二進(jìn)制位為1，則計(jì)算
            tmp *= tmp;     //記錄中間結(jié)果
        }
        return n<0 ? 1/product/x : product;     //正負(fù)及邊界處理
    }
}