实现 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] 。

解法一：递归+分治

快速次方的定义就是利用已知的n/2次幂求出n次幂。可以用递归+分治的方法得出。注意在分治过程中要正确处理n/2不能整除的情况，即当n/2不能整除时，分治可以拆成 x*x，之后对n-1次幂进行分治。
另外这题还要注意负次幂的情况，应将问题转化为正次幂的倒数。

  1. class Solution:
  2.     def myPow(self, x: float, n: int) -> float:
  3.         if n == 0:
  4.             return 1
  5.         if n < 0:
  6.             return 1 / self.myPow(x, -n)
  7.         if n % 2 :
  8.             return  x * self.myPow(x, n - 1)
  9.         return self.myPow(x * x, n / 2)

解法二：迭代

递归法都是尾递归。通过观察尾递归的模式，发现需要压栈的关键信息是当前值是否能被2整除。因此可以改写为使用栈进行迭代的方式。

  1. class Solution:
  2.     def myPow(self, x: float, n: int) -> float:
  3.         stack, temp, neg, n = [], 1, n > 0, abs(n)
  4.         while n:
  5.             stack.append(n % 2)
  6.             n //= 2
  7.         while stack:
  8.             temp *= temp * (not stack.pop() or x)
  9.         return temp if neg else 1 / temp