实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例- 输入：x = 2.00000, n = 10
- 输出：1024.00000
- -100.0 < x < 100.0
- -2的31次方 <= n <= 2的31次方 -1
- -10的4次方 <= x的n次方 <= 10的4方
「快速幂算法」的本质是分治算法。
以示例为例，从 2 开始，每次直接把上一次的结果进行平方，计算3次就可以得到2的10次方值，我们可以按照：
- x → x的2次方 → x的5次方 → x的10次方的顺序。
直接从左到右进行推导看上去很困难，因为在每一步中，我们不知道在将上一次的结果平方之后，还需不需要额外乘 x。但如果我们从右往左看，分治的思想就十分明显了。
代码如下：
- 时间复杂度：O(logn)，即为递归的层数（由于每次递归都会使得指数减少一半）。
- 空间复杂度：O(logn)，即为递归的层数。这是由于递归的函数调用会使用栈空间。
由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。
我们以 x 的77次方 作为例子：
- x → x的2次方 → x的4次方→ x的9次方 → x的19次方 → x的38次方 → x的77次方；
可以发现：
- x的38次方 到 x的77次方 中额外乘的 x 在 x的77次方 中贡献了 x；
- x的9次方 到 x的19次方 中额外乘的 x 在 之后被平方了 2 次，因此在 x的77次方 中贡献了 x的4次方；
- x的4次方 到 x的9次方 中额外乘的 x 在之后被平方了 3 次， 因此在 x的77次方 中贡献了 x的8次方；
- 最初的 x 在之后被平方了 6 次，因此在 x的77次方 中贡献了 x的64次方。
我们把这些贡献相乘，x * x的4次方 * x的8次方 * x的64次方 恰好等于 x的77次方。而这些贡献的指数部分又是什么呢？它们都是 2 的幂次，这是因为每个额外乘的 x 在之后都会被平方若干次。而这些指数 1，4，8 和 64，恰好就对应了 77 的二进制表示 (1001101)2 中的每个 1！
这样以来，我们从 x 开始不断地进行平方，如果 n 的第 k 个（从右往左，从 0 开始计数）二进制位为 1，那么我们就将对应的贡献
x的(2的k次方)次方 计入答案。
代码如下：
- 时间复杂度：O(logn)，即为对 n 进行二进制拆分的时间复杂度。
- 空间复杂度：O(1)。
本文内容出处是力扣官网，希望和大家一起刷算法，在后面的路上不变秃但是变强！
好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。
,
