Medium
这道题要先处理n为奇偶和n为正负，难在处理edge case.
比如当n = Integer.MIN_VALUE时怎么办？-2147483648 - 2147483647
要知道 -Integer.MIN_VALUE = Integer.MIN_VALUE这个等式. 然后这里的解法比较巧妙，n为负数的时候直接先加一再取负，这样永远也不可能溢出. 减了一相当于1/x少算了一次幂，那我们就返回的答案多乘以一个1/x就好了；
处理n为正数时，考虑奇偶两种情况。n为偶数很简单，就比如2^4 = 4^2 = 16^1, x^n = (x2)(n/2).这样每次除二经过logn之后会得到n = 1, n = 0结束递归. 如果n是奇数，那么n - 1是偶数. 因为n -1次幂相对n少乘了一个x, 所以我们返回的结果多乘一个x就好了，返回x * myPow(x*x, n/2).
class Solution {
public double myPow(double x, int n){
if (x == 0){
return 0;
}
if (n == 0 || x == 1){
return 1;
}
if (n < 0){
n = -(n + 1);
x = 1/x;
return x * myPow(x, n);
}
if (n % 2 == 0){
return myPow(x*x, n/2);
} else {
return x * myPow(x*x, n/2);
}
}
}
