# 0050. Pow(x, n) ## 题目地址（50. Pow(x, n)） <https://leetcode-cn.com/problems/powx-n/description/> ## 题目描述 ``` <pre class="calibre18">``` 实现 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)O(N)O(N)。 经实际测试，这种做法果然超时了。测试用例通过 291/304，在 `0.00001\n2147483647`这个测试用例挂掉了。如果是面试，这个解法可以作为一种兜底解法。 ### 代码 语言支持: Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">myPow</span><span class="hljs-params">(self, x: float, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n < <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> / self.myPow(x, -n) res = <span class="hljs-params">1</span> <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n): res *= x <span class="hljs-keyword">return</span> 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: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">myPow</span><span class="hljs-params">(self, x: float, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> x <span class="hljs-keyword">if</span> n < <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> / self.myPow(x, -n) <span class="hljs-keyword">return</span> self.myPow(x, n // <span class="hljs-params">2</span>) * self.myPow(x, n - n // <span class="hljs-params">2</span>) ``` ``` ## 解法二 - 优化递归 ### 思路 上面的解法每次直接 myPow 都会调用两次自己。我们不从缓存计算角度，而是从减少这种调用的角度来优化。 我们考虑 myPow 只调用一次自身可以么？ 没错，是可以的。 我们的思路就是： - 如果 n 是偶数，我们将 n 折半，底数变为 x^2 - 如果 n 是奇数， 我们将 n 减去 1 ，底数不变，得到的结果再乘上底数 x 这样终于可以 AC。 ### 代码 语言支持: Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">myPow</span><span class="hljs-params">(self, x: float, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> <span class="hljs-keyword">if</span> n == <span class="hljs-params">1</span>: <span class="hljs-keyword">return</span> x <span class="hljs-keyword">if</span> n < <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> / self.myPow(x, -n) <span class="hljs-keyword">return</span> self.myPow(x _ x, n // <span class="hljs-params">2</span>) <span class="hljs-keyword">if</span> n % <span class="hljs-params">2</span> == <span class="hljs-params">0</span> <span class="hljs-keyword">else</span> x _ self.myPow(x, n - <span class="hljs-params">1</span>) ``` ``` ## 解法三 - 位运算 ### 思路 我们来从位（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: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">myPow</span><span class="hljs-params">(self, x: float, n: int)</span> -> float:</span> <span class="hljs-keyword">if</span> n < <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">1</span> / self.myPow(x, -n) res = <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> n: <span class="hljs-keyword">if</span> n & <span class="hljs-params">1</span> == <span class="hljs-params">1</span>: res *= x x *= x n >>= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> res ``` ``` **复杂度分析** - 时间复杂度：O(logN)O(logN)O(logN) - 空间复杂度：O(1)O(1)O(1) ## 关键点解析 - 超时分析 - hashtable - 数学分析 - 位运算 - 二进制转十进制 ## 相关题目 - [458.可怜的小猪](https://leetcode-cn.com/problems/poor-pigs/description/)  大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。