【思路1-Java】递归实现

采用递归实现，那么本题的终止条件是 n == 0 和 n == 1。这里不采用下面的做法：

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;
    }
}

因为时间复杂度为 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 / 2) * myPow(x, n / 2);
    }
}
时间复杂度真的下降为 O(logn)了吗？非也，由于递归的特性——无法记录下中间结果， myPow(x, n / 2) 被计算了两次，因此复杂度为 O(log(2^n)) = O(n)，也会超时。

我们最好用一个值两记录下中间变量，充分利用好中间结果，克服这种毛病。

另外，本题的难点主要是在边界条件：如果 n < 0，是不是 n = -n， x = 1 / x ，再进行递归就能解决了呢？如果 n = Intege.MIN_VALUE，n = -n 会出现溢出，怎么办呢？我们可以先将 n / 2 赋值给 t，再将 t = -n，就不会出现溢出问题。

public class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        int t = n / 2;
        if(n < 0) {
            t = -t;
            x = 1 / x;
        }
        double res = myPow(x, t);
        if(n % 2 == 0) return res * res;
        return res * res * x;
    }
}
300 / 300 test
 cases passed. Runtime: 1
 ms  Your runtime beats 34.94% of javasubmissions.

【思路2-Java】非递归实现
这种做法如何理解呢？加入 n = 13，13在二进制中表示为：00001101，那么13 = 2^3 + 2^2 + 2^0



public class Solution {
    public double myPow(double x, int n) {
        int m = n < 0 ? -n - 1 : n;  //如果是n负数，要避免n=<span style="font-family: Arial, Helvetica, sans-serif;">-2147483648</span><span style="font-family: Arial, Helvetica, sans-serif;">溢出</span>
        double p = 1;
        for(double q = x; m > 0; m /= 2) {  
            if((m & 1) != 0) p *= q;  //一旦该位为1，那么将q乘入p中
            q *= q;  //m每次除2，q就要变为平方
        }
        return n < 0 ? 1 / p / x : p;
    }
}
300 / 300 test
 cases passed. Runtime: 1 ms  Your runtime beats 34.94% of javasubmissions.