參考資料：左程云算法課 ， 《程序員代碼面試指南》
50. Pow(x, n)
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
思路：
以求
1
0
75
10^{75}
1075為例，
75
=
64
+
8
+
2
+
1
=
(
1001011
)
2
75 = 64+8+2+1=(1001011)_2
75=64+8+2+1=(1001011)2?
so,
1
0
75
=
1
0
64
×
1
?
1
0
32
×
0
?
1
0
16
×
0
?
1
0
8
×
1
?
1
0
4
×
0
?
1
0
2
×
1
?
1
0
1
×
1
=
1
0
(
1001011
)
2
10^{75}=10^{64\times1}·10^{32\times0}·10^{16\times0}·10^{8\times1}·10^{4\times0}·10^{2\times1}·10^{1\times1}=10^{ (1001011)_2}
1075=1064×1?1032×0?1016×0?108×1?104×0?102×1?101×1=10(1001011)2?
we assume that base=10, res=1.
二進(jìn)制表示的最低位(最右邊的那一位)是1， 那么
r
e
s
=
r
e
s
×
b
a
s
e
=
10
,
b
a
s
e
=
b
a
s
e
×
b
a
s
e
=
1
0
2
res = res \times base = 10, base = base\times base=10^2
res=res×base=10,base=base×base=102
二進(jìn)制表示的倒數(shù)第二位是0，那么
r
e
s
=
r
e
s
=
10
,
b
a
s
e
=
b
a
s
e
×
b
a
s
e
=
1
0
4
res = res = 10, base = base\times base=10^4
res=res=10,base=base×base=104
and so on. we can get the ans, which is the final 'res`.文章來源：http://www.zghlxwxcb.cn/news/detail-480056.html
注：整數(shù)的冪可以擴(kuò)展到矩陣的冪， 把res的起點設(shè)置為單位矩陣即可。矩陣冪的應(yīng)用見斐波那契數(shù)列相關(guān)問題（詳細(xì)可查閱《程序員代碼面試指南》）。
注2： 這道題要考慮到冪可能取負(fù)數(shù)。對于普通負(fù)數(shù)，我們也可以直接取相反數(shù)，計算得結(jié)果后再取倒數(shù)即可；特別要注意的是，冪可能取到 系統(tǒng)最小值， 這時直接取相反數(shù)還是 系統(tǒng)最小指 它自身，于是需要特別處理，大致思路是
x
M
I
N
=
x
M
I
N
+
1
/
x
x^{MIN} = x^{MIN+1}/x
xMIN=xMIN+1/x，而
x
M
I
N
+
1
x^{MIN+1}
xMIN+1是一種普通情況可以調(diào)用當(dāng)前這個函數(shù)解決。
詳細(xì)見代碼。文章來源地址http://www.zghlxwxcb.cn/news/detail-480056.html
public double myPow(double x, int n){
if(x==0||x==1){return x;}
if(n==0){return 1;}
// there exists one case "x=2.00000, n=-2147483648"
if(n==Integer.MIN_VALUE)
{
if(x>1 || x<-1){return 0;}
return myPow(x,n+1)/x;
}
boolean isPos = true;
if(n<0)
{
isPos=false;
n =-n;
}
double base=x;
double res = 1;
for(;n!=0;n>>=1)
{
if((n&1)==1)
{
res*=base;
}
base = base*base;
}
return isPos?res:1/res;
}
到了這里，關(guān)于LeetCode ! 50. Pow(x, n)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
