实现 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
• -2^31 <= n <= 2^31-1
• -10^4 <= xn <= 10^4

分析：

方法1：快速幂+迭代

先简单介绍一下快速幂，比如说 x = 2， n 为 10，n 转化为二进制就是1010，那么输出的就为 2^(1010) = 2^(1*2^3 + 0*2^2 + 1*2^1 +  0*2^0) = 2^(2^3) * 2^2，本来 O(n) 的时间复杂度就降到了 O(log n)，那么我们可以将每一位的运算看做 x *= x，那么有 1 的情况就是例外，单独乘起来，最后将这个单独乘的变量和结果相乘就是答案。判断是否有 1 可以直接和 1 做与运算，然后将 n 右移，直到 n = 1。需要注意的是，n 为负数时取反，然后将 x 令为 1/x 即可，但是取反时可能越界，索引将 n 的类型转化为长整型（long）。

时间复杂度：O(log n)
空间复杂度：O(1)

class Solution {public double myPow(double x, int n) {//任何数的零次方都是 1if(n == 0){return 1.0;}//防止 n 取反时越界long n2 = n;// n 小于零取反，x 取倒数if(n < 0){x = 1 / x;n2 = -n2;}//定义结果double sum = 1.0;while(n2 != 1){//取余为 1 时if((n2 & 1) == 1){sum *= x;}x *= x;//右移一位n2 >>= 1;}return sum * x;}
}

方法2：快速幂+递归

时间复杂度：O(log n)
空间复杂度：O(1)

class Solution {public double myPow(double x, int n) {//任何数的零次方都是 1if(n == 0){return 1.0;}//n 为负数情况if(n == -1){return 1 / x;}//n 为正数if(n == 1){return x;}return myPow(x * x, n >> 1) * myPow(x, n & 1);}
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof