Pow(x, n)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
示例 2:
输入: 2.10000, 3
输出: 9.26100
示例 3:
输入: 2.00000, -2
输出: 0.25000
解释:
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
解法 1
暴力法，x 的 n 次幂就是 n 个 x 相乘，注意处理 n 为负数的情况，需要将 x 变为 x 的倒数，再将 n 变为正数
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
for i in range(n):
ans = ans * x
return ans
执行用时：超出时间限制
时间复杂度：O(n)，我们需要将 x 累乘 n 次。
空间复杂度：O(1)，我们只需要一个变量来保存最终 x 的累乘结果。
解法 2
利用递归实现分治法，我们可以根据幂的奇偶来将公式拆解，使得运算数值尽可能小，从而提升运算速度，若为偶数 ，若为奇数
，注意若 n 为负数，
。当 n 为 1 时返回 x，这是递归的出口。另外，需要注意 x = 0 或 1，n = 0 或 1，n < 0 等情况。
def my_pow(x, n):
if n == 0:
return 1.0
if n == 1:
return x
if n < 0:
return 1 / my_pow(x, -n)
if n % 2:
return x * my_pow(x, n - 1)
return my_pow(x * x, n / 2)
执行用时 :40 ms
内存消耗 :13.7 MB
时间复杂度：O(log n)，每一次我们使用公式 ，n 都变为原来的一半。因此我们需要最多 O(log n) 次操作来得到结果。
空间复杂度：O(log n)，每一次计算，我们需要存储 的结果。 我们需要计算 O(log n) 次，所以空间复杂度为 O(log n) 。
解法 3
利用迭代实现二进制拆分，由于递归需要使用额外的栈空间，我们可以将递归转写为迭代。我们观察一下 n 的二进制表示，假设 n = 77，二进制表示为 1001101，将其包含 1 的部分拆分为 1000000 0001000 0000100 0000001。其中，1000000 的十进制表示为 64，0001000 的十进制表示为 8，0000100 的十进制表示为 4，0000001 的十进制表示为 1，而一个数 恰好等于
。那么，如果计算一个数 x 的 n 次幂，就可以从 x 开始不断地进行平方，得到
如果 n 的第 k 个（从右往左，从 0 开始计数）二进制位为 1，那么我们就将
计入结果，注意是从 0 开始计数，如果 n 的二进制第 0 位为 1，则将
计入结果，并全部累乘得到最终结果。
def my_pow(x, n):
if n < 0:
x = 1 / x
n = -n
ans = 1
while n > 0:
if n & 1:
ans *= x
x *= x
n >>= 1
return ans
执行用时 :44 ms
内存消耗 :13.8 MB
时间复杂度：O(log n)，对 n 进行二进制拆分的时间复杂度。
空间复杂度：O(1)
