0050. 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:
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:
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, CPP
Python3 Code:
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)
CPP Code:
class Solution {
double myPow(double x, long n) {
if (n < 0) return 1 / myPow(x, -n);
if (n == 0) return 1;
if (n == 1) return x;
if (n == 2) return x * x;
return myPow(myPow(x, n / 2), 2) * (n % 2 ? x : 1);
}
public:
double myPow(double x, int n) {
return myPow(x, (long)n);
}
};
复杂度分析
- 时间复杂度:$O(logN)$
- 空间复杂度:$O(logN)$
以 x 的 10 次方举例。10 的 2 进制是 1010,然后用 2 进制转 10 进制的方法把它展成 2 的幂次的和。

