题目
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题方法
暴力解法
时间复杂度 O（n） 空间复杂度O（1）
分治（二分法） + 迭代/递归
时间复杂度 O(logn) n是幂，每次对幂减半 空间复杂度O（1）
迭代代码助解：
2^5 = 2 * 2 * 2 * 2 * 2 = 2^2 * 2^2 * 2
初始化： x = 2 n = 5 pow = 1
循环条件 n > 0：
第一次：
n = 5 ,5为奇数 pow *= x = 2 ,x = 4
第二次：
n = 2 ,2为偶数 pow = 2 ,x = 16
第三次：
n = 1 ,1为奇数 pow *= x = 32 ,x = 256
n = 0 循环结束 返回结果pow = 32
递归代码助解：
终止条件：n = 0 返回 1
递归处理:如果n为偶数，返回上一步递归结果的平方
如果n为奇数，返回上一步递归结果的平方再乘x
递：
1.x = 2,n = 5
2.x = 2,n = 2
3.x = 2,n = 1
4.x = 2,n = 0
归：
4. n = 0 返回结果 1
3. n = 1 返回 上一步递归结果 1 * 1 因为1是奇数返回结果还要乘x,所以返回结果为 2
2. n = 2 返回 上一步递归结果 2 * 2 = 4
1. n = 5 返回 上一步递归结果 4 * 4 = 16 因为5是奇数 最终返回结果为 16 * 2 = 32
代码
// 暴力解法 时间复杂度O（n） 空间复杂度O（1）
func myPow(x float64, n int) float64 {
if n < 0{
x = 1/x
n = -n
}
var ans float64 = 1
for i:=0;i < n;i++{
ans *= x
}
return ans
}
// 分治 迭代
func myPow2(x float64,n int) float64 {
// 如果n=0直接返回1
if n == 0{
return 1
}
// 如果n为负数进行处理
if n < 0{
x = 1/x
n = -n
}
// 返回值
var pow float64 = 1
// 当n小于0时结束循环
for n > 0 {
// 如果n为奇数，返回值还要乘剩下的x
if n & 1 == 1{
pow *= x
}
x *= x
// 相当于n/2
n = n>>1
}
return pow
}
// 二分法 递归
func myPow3(x float64,n int) float64 {
// 当n=0结束递归
if n == 0 {
return 1
}
newX := x
newN := n
if n < 0{
newX = 1/newX
newN = -n
}
temp := myPow3(newX,newN/2)
res := temp * temp
// 奇数情况
if newN % 2 != 0 {
res *= newX
}
return res
}