<div>
Implement pow(x, n), which calculates x raised to the power n (i.e., x<sup>n</sup>).
Example 1:
<pre>Input: x = 2.00000, n = 10 Output: 1024.00000 </pre>
Example 2:
<pre>Input: x = 2.10000, n = 3 Output: 9.26100 </pre>
Example 3:
<pre>Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2<sup>-2</sup> = 1/2<sup>2</sup> = 1/4 = 0.25 </pre>
Constraints:
-100.0 < x < 100.0-2<sup>31</sup> <= n <= 2<sup>31</sup>-1-10<sup>4</sup> <= x<sup>n</sup> <= 10<sup>4</sup>
</div>
题目大意：
求幂
解题思路：
DFS
解题步骤：
N/A
注意事项：
- 保存dfs(x, n/2)的临时结果，避免重复计算
- n可以是0，负数
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17def myPow(self, x: float, n: int) -> float:
if n >= 0:
return self.dfs(x, n)
else:
return self.dfs(1 / x, -n)
def dfs(self, x, n):
if n == 0:
return 1
if n == 1:
return x
if n % 2 == 0:
tmp = self.dfs(x, n / 2)
return tmp * tmp
else:
tmp = self.dfs(x, (n - 1) / 2)
return tmp * tmp * x
算法分析：
时间复杂度为O(logn)，空间复杂度O(1)
