LeetCode 050 Pow(x, n)

LeetCode

Implement pow(x, n), which calculates x raised to the power n (i.e., x<sup>n</sup>).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

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>

题目大意：

求幂

解题思路：

DFS

解题步骤：

N/A

注意事项：

1. 保存dfs(x, n/2)的临时结果，避免重复计算
2. n可以是0，负数

Python代码：

def 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)