實現(xiàn) pow(x, n) ，即計算 x 的 n 次冪函數(shù)（即，xn）。不得使用庫函數(shù)，同時不需要考慮大數(shù)問題。

示例

• 輸入：x = 2.00000, n = 10

• 輸出：1024.00000

提示

• -100.0 < x < 100.0

• -2的31次方 <= n <= 2的31次方 -1

• -10的4次方 <= x的n次方 <= 10的4方

方法一：快速冪 + 遞歸

「快速冪算法」的本質(zhì)是分治算法。

以示例為例，從 2 開始，每次直接把上一次的結(jié)果進(jìn)行平方，計算3次就可以得到2的10次方值，我們可以按照：

• x → x的2次方 → x的5次方 → x的10次方的順序。

直接從左到右進(jìn)行推導(dǎo)看上去很困難，因為在每一步中，我們不知道在將上一次的結(jié)果平方之后，還需不需要額外乘 x。但如果我們從右往左看，分治的思想就十分明顯了。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(logn)，即為遞歸的層數(shù)（由于每次遞歸都會使得指數(shù)減少一半）。

• 空間復(fù)雜度：O(logn)，即為遞歸的層數(shù)。這是由于遞歸的函數(shù)調(diào)用會使用棧空間。

方法二：快速冪 + 迭代

由于遞歸需要使用額外的?？臻g，我們試著將遞歸轉(zhuǎn)寫為迭代。

我們以 x 的77次方 作為例子：

• x → x的2次方 → x的4次方→ x的9次方 → x的19次方 → x的38次方 → x的77次方；

可以發(fā)現(xiàn)：

• x的38次方 到 x的77次方 中額外乘的 x 在 x的77次方 中貢獻(xiàn)了 x；

• x的9次方 到 x的19次方 中額外乘的 x 在 之后被平方了 2 次，因此在 x的77次方 中貢獻(xiàn)了 x的4次方；

• x的4次方 到 x的9次方 中額外乘的 x 在之后被平方了 3 次， 因此在 x的77次方 中貢獻(xiàn)了 x的8次方；

• 最初的 x 在之后被平方了 6 次，因此在 x的77次方 中貢獻(xiàn)了 x的64次方。

我們把這些貢獻(xiàn)相乘，x * x的4次方 * x的8次方 * x的64次方 恰好等于 x的77次方。而這些貢獻(xiàn)的指數(shù)部分又是什么呢？它們都是 2 的冪次，這是因為每個額外乘的 x 在之后都會被平方若干次。而這些指數(shù) 1，4，8 和 64，恰好就對應(yīng)了 77 的二進(jìn)制表示 (1001101)2 中的每個 1！

這樣以來，我們從 x 開始不斷地進(jìn)行平方，如果 n 的第 k 個（從右往左，從 0 開始計數(shù)）二進(jìn)制位為 1，那么我們就將對應(yīng)的貢獻(xiàn)

x的(2的k次方)次方 計入答案。

代碼如下：

復(fù)雜度分析

• 時間復(fù)雜度：O(logn)，即為對 n 進(jìn)行二進(jìn)制拆分的時間復(fù)雜度。

• 空間復(fù)雜度：O(1)。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。