實(shí)現(xiàn) pow(x, n) 碎连，即計(jì)算 x 的 n 次冪函數(shù)绑莺。
示例 1:
輸入: 2.00000, 10
輸出: 1024.00000
示例 2:
輸入: 2.10000, 3
輸出: 9.26100
示例 3:
輸入: 2.00000, -2
輸出: 0.25000
解釋:
說明:
-100.0 < x < 100.0
n 是 32 位有符號(hào)整數(shù)妆偏，其數(shù)值范圍是 [?231, 231 ? 1] 我磁。
解法 1
暴力法圃阳，x 的 n 次冪就是 n 個(gè) x 相乘厌衔，注意處理 n 為負(fù)數(shù)的情況，需要將 x 變?yōu)?x 的倒數(shù)捍岳，再將 n 變?yōu)檎龜?shù)
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
for i in range(n):
ans = ans * x
return ans
執(zhí)行用時(shí)：超出時(shí)間限制
時(shí)間復(fù)雜度：O(n)富寿，我們需要將 x 累乘 n 次。
空間復(fù)雜度：O(1)锣夹，我們只需要一個(gè)變量來保存最終 x 的累乘結(jié)果页徐。
解法 2
利用遞歸實(shí)現(xiàn)分治法，我們可以根據(jù)冪的奇偶來將公式拆解银萍，使得運(yùn)算數(shù)值盡可能小变勇，從而提升運(yùn)算速度，若為偶數(shù) 贴唇，若為奇數(shù)
搀绣，注意若 n 為負(fù)數(shù)，
戳气。當(dāng) n 為 1 時(shí)返回 x链患，這是遞歸的出口。另外瓶您，需要注意 x = 0 或 1麻捻，n = 0 或 1，n < 0 等情況呀袱。
def my_pow(x, n):
if n == 0:
return 1.0
if n == 1:
return x
if n < 0:
return 1 / my_pow(x, -n)
if n % 2:
return x * my_pow(x, n - 1)
return my_pow(x * x, n / 2)
執(zhí)行用時(shí) :40 ms
內(nèi)存消耗 :13.7 MB
時(shí)間復(fù)雜度：O(log n)贸毕，每一次我們使用公式 ，n 都變?yōu)樵瓉淼囊话胍拐浴Ｒ虼宋覀冃枰疃?O(log n) 次操作來得到結(jié)果明棍。
空間復(fù)雜度：O(log n)，每一次計(jì)算油吭，我們需要存儲(chǔ) 的結(jié)果击蹲。 我們需要計(jì)算 O(log n) 次署拟，所以空間復(fù)雜度為 O(log n) 。
解法 3
利用迭代實(shí)現(xiàn)二進(jìn)制拆分歌豺，由于遞歸需要使用額外的椡魄睿空間，我們可以將遞歸轉(zhuǎn)寫為迭代类咧。我們觀察一下 n 的二進(jìn)制表示馒铃，假設(shè) n = 77，二進(jìn)制表示為 1001101痕惋，將其包含 1 的部分拆分為 1000000 0001000 0000100 0000001区宇。其中，1000000 的十進(jìn)制表示為 64值戳，0001000 的十進(jìn)制表示為 8议谷，0000100 的十進(jìn)制表示為 4，0000001 的十進(jìn)制表示為 1堕虹，而一個(gè)數(shù) 恰好等于
卧晓。那么，如果計(jì)算一個(gè)數(shù) x 的 n 次冪赴捞，就可以從 x 開始不斷地進(jìn)行平方逼裆，得到
如果 n 的第 k 個(gè)（從右往左，從 0 開始計(jì)數(shù)）二進(jìn)制位為 1赦政，那么我們就將
計(jì)入結(jié)果胜宇，注意是從 0 開始計(jì)數(shù)，如果 n 的二進(jìn)制第 0 位為 1恢着，則將
計(jì)入結(jié)果桐愉，并全部累乘得到最終結(jié)果。
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
while n > 0:
if n & 1:
ans *= x
x *= x
n >>= 1
return ans
執(zhí)行用時(shí) :44 ms
內(nèi)存消耗 :13.8 MB
時(shí)間復(fù)雜度：O(log n)掰派，對(duì) n 進(jìn)行二進(jìn)制拆分的時(shí)間復(fù)雜度仅财。
空間復(fù)雜度：O(1)
