Pow(x, n)
作者：由 白龍魚服 發表于 歷史時間：2021-04-15
原題指路
力扣
解題思路
看到pow函式，上來就是一個快速冪。
快速冪遞迴式
然後，就是將遞迴式改寫為非遞迴版本，透過對指數進行二進位制轉換，然後不斷右移即可模擬這個過程（因為其實本體是二分法啦）。 若指數為負，那麼就先計算$x^{-n}$，然後再取倒數即可。
時間複雜度：
空間複雜度：
程式碼
class
Solution
：
def
myPow
（
self
，
x
：
float
，
n
：
int
）
->
float
：
‘’‘
快速冪
Args：
x： 底數
n： 指數（整數）
Returns：
x^n
’‘’
def
qpow
（
N
：
int
）
->
float
：
‘’‘
當指數為正整數時的快速冪
Args：
N： 指數
Returns：
x^N
’‘’
res
=
1。0
num
=
x
while
N
>
0
：
if
N
%
2
：
# 最後一位為1則代表需要乘
res
*=
num
num
*=
num
# 更新乘數
N
>>=
1
# 更新指數
return
res
return
qpow
（
n
）
if
n
>=
0
else
1。0
/
qpow
（
-
n
）
# 當n為負數時可以先計算x^（-n）然後再取倒數
