## 題目地址（50. Pow(x, n)） https://leetcode-cn.com/problems/powx-n/description/ ## 題目描述 > 實現?pow(x, n)?，即計算 x 的 n 次冪函數。 示例 1: 輸入: 2.00000, 10 輸出: 1024.00000 示例?2: 輸入: 2.10000, 3 輸出: 9.26100 示例?3: 輸入: 2.00000, -2 輸出: 0.25000 解釋: 2-2 = 1/22 = 1/4 = 0.25 說明: -100.0 <?x?< 100.0 n?是 32 位有符號整數，其數值范圍是?[?231,?231?? 1] 。 ## 前置知識 - 遞歸 - 位運算 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 解法零 - 遍歷法 ### 思路 這道題是讓我們實現數學函數`冪`，因此直接調用系統內置函數是不被允許的。 符合直覺的做法是`將x乘以n次`，這種做法的時間復雜度是$O(N)$。 經實際測試，這種做法果然超時了。測試用例通過 291/304，在 `0.00001\n2147483647`這個測試用例掛掉了。如果是面試，這個解法可以作為一種兜底解法。 ### 代碼 語言支持: Python3 Python3 Code: ```python class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1 if n < 0: return 1 / self.myPow(x, -n) res = 1 for _ in range(n): res *= x return res ``` ## 解法一 - 普通遞歸（超時法） ### 思路 首先我們要知道： - 如果想要求 x ^ 4，那么我們可以求 (x^2)^2 - 如果是奇數，會有一點不同。 比如 x ^ 5 就等價于 x \* (x^2)^2。 > 當然 x ^ 5 可以等價于 (x ^ 2) ^ 2.5, 但是這不相當于直接調用了冪函數了么。對于整數，我們可以很方便的模擬，但是小數就不方便了。 我們的思路就是： - 將 n 地板除 2，我們不妨設結果為 a - 那么 myPow(x, n) 就等價于 `myPow(x, a) * myPow(x, n - a)` 很可惜這種算法也會超時，原因在于重復計算會比較多，你可以試一下緩存一下計算看能不能通過。 > 如果你搞不清楚有哪些重復計算，建議畫圖理解一下。 ### 代碼 語言支持: Python3 Python3 Code: ```python class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1 if n == 1: return x if n < 0: return 1 / self.myPow(x, -n) return self.myPow(x, n // 2) * self.myPow(x, n - n // 2) ``` ## 解法二 - 優化遞歸 ### 思路 上面的解法每次直接 myPow 都會調用兩次自己。我們不從緩存計算角度，而是從減少這種調用的角度來優化。 我們考慮 myPow 只調用一次自身可以么？ 沒錯，是可以的。 我們的思路就是： - 如果 n 是偶數，我們將 n 折半，底數變為 x^2 - 如果 n 是奇數， 我們將 n 減去 1 ，底數不變，得到的結果再乘上底數 x 這樣終于可以 AC。 ### 代碼 語言支持: Python3 Python3 Code: ```python class Solution: def myPow(self, x: float, n: int) -> float: if n == 0: return 1 if n == 1: return x if n < 0: return 1 / self.myPow(x, -n) return self.myPow(x _ x, n // 2) if n % 2 == 0 else x _ self.myPow(x, n - 1) ``` ## 解法三 - 位運算 ### 思路 我們來從位（bit）的角度來看一下這道題。如果你經常看我的題解和文章的話，可能知道我之前寫過幾次相關的“從位的角度思考分治法”，比如 LeetCode [458.可憐的小豬](https://leetcode-cn.com/problems/poor-pigs/description/)。 以 x 的 10 次方舉例。10 的 2 進制是 1010，然后用 2 進制轉 10 進制的方法把它展成 2 的冪次的和。   因此我們的算法就是： - 不斷的求解 x 的 2^0 次方，x 的 2^1 次方，x 的 2^2 次方等等。 - 將 n 轉化為二進制表示 - 將 n 的二進制表示中`1的位置`pick 出來。比如 n 的第 i 位為 1，那么就將 x^i pick 出來。 - 將 pick 出來的結果相乘  這里有兩個問題： 第一個問題是`似乎我們需要存儲 x^i 以便后續相乘的時候用到`。實際上，我們并不需要這么做。我們可以采取一次遍歷的方式來完成，具體看代碼。 第二個問題是，如果我們從低位到高位計算的時候，我們如何判斷最高位置是否為 1？我們需要一個 bitmask 來完成，這種算法我們甚至需要借助一個額外的變量。 然而我們可以 hack 一下，直接從高位到低位進行計算，這個時候我們只需要判斷最后一位是否為 1 就可以了，這個就簡單了，我們直接和 1 進行一次`與運算`即可。 ### 代碼 語言支持: Python3 Python3 Code: ```python class Solution: def myPow(self, x: float, n: int) -> float: if n < 0: return 1 / self.myPow(x, -n) res = 1 while n: if n & 1 == 1: res *= x x *= x n >>= 1 return res ``` **復雜度分析** - 時間復雜度：$O(logN)$ - 空間復雜度：$O(1)$ ## 關鍵點解析 - 超時分析 - hashtable - 數學分析 - 位運算 - 二進制轉十進制 ## 相關題目 - [458.可憐的小豬](https://leetcode-cn.com/problems/poor-pigs/description/)  大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：https://github.com/azl397985856/leetcode 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。