Medium
這道題要先處理n為奇偶和n為正負(fù)，難在處理edge case.
比如當(dāng)n = Integer.MIN_VALUE時(shí)怎么辦昵宇？-2147483648 - 2147483647
要知道 -Integer.MIN_VALUE = Integer.MIN_VALUE這個(gè)等式. 然后這里的解法比較巧妙领斥，n為負(fù)數(shù)的時(shí)候直接先加一再取負(fù)，這樣永遠(yuǎn)也不可能溢出. 減了一相當(dāng)于1/x少算了一次冪鳍悠，那我們就返回的答案多乘以一個(gè)1/x就好了；
處理n為正數(shù)時(shí)坐搔，考慮奇偶兩種情況藏研。n為偶數(shù)很簡單，就比如2^4 = 4^2 = 16^1, x^n = (x2)(n/2).這樣每次除二經(jīng)過logn之后會(huì)得到n = 1, n = 0結(jié)束遞歸. 如果n是奇數(shù)概行，那么n - 1是偶數(shù). 因?yàn)閚 -1次冪相對n少乘了一個(gè)x, 所以我們返回的結(jié)果多乘一個(gè)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);
}
}
}
