T50. Pow(x, n)【Medium】
題目
寫一個(gè) pow(x,n) 方法轩猩。
思路
pow(x,n) 方法就是算 x 的 n 次方箱硕。
分為三種情況：
① n=0 時(shí)：
返回 1
② n>0 時(shí)：
一般想補(bǔ)救是一個(gè)個(gè)乘起來嘛喻杈，但是簡單的乘起來可能超時(shí)勾栗。
這里用遞歸時(shí)間復(fù)雜度比較低路鹰，
就是比如 3 的 5 次方贷洲，不要用 3×3×3×3×3，而是 3×（3×3）2
若 n 偶數(shù)和奇數(shù)時(shí)處理方法不一樣晋柱，看代碼就好~
③ n<0 時(shí):
把 x=1/x ,n = -n, 這樣以后就和 情況 ② 一樣了
代碼
代碼取自 Top Solution优构，稍作注釋
public double myPow(double x, int n) {
//等于0返回1
if(n == 0)
return 1;
//小于0, x取反，變成和正的時(shí)候的一樣
if(n<0){
n = -n;
x = 1/x;
//解決MIN_VALUE的問題
if (n == Integer.MIN_VALUE) {
n = Integer.MAX_VALUE;
x *= x;
}
}
//遞歸,注意對(duì)偶數(shù)和奇數(shù)的處理
return (n%2 == 0) ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}
補(bǔ)充
一定會(huì)有人不明白下面代碼的用意（就和之前的我一樣哈哈哈）：
//解決MIN_VALUE的問題
if (n == Integer.MIN_VALUE) {
n = Integer.MAX_VALUE;
x *= x;
}
大家都記得老師似乎講過的 int 的范圍：-2147483648 ~ +2147483647
細(xì)心的人會(huì)發(fā)現(xiàn)負(fù)的要多一個(gè)數(shù)雁竞，因?yàn)橛疫叺木幋a有一個(gè)給 0 了钦椭。
我運(yùn)行了一下,下面的程序
System.out.print(-2147483648); --》-2147483648
System.out.print(-(-2147483648)); --》-2147483648
兩個(gè)輸出是一樣的，所以這里要另行處理碑诉。
當(dāng) n == Integer.MIN_VALUE 時(shí)彪腔，取反就用 n= Integer.MAX_VALUE，
因?yàn)閿?shù)字夠大进栽，所以一般不用管它們兩個(gè)實(shí)際差一那么一點(diǎn)點(diǎn)的差別德挣。
