50 Pow(x, n)（快速幂）

1. 问题描述：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/powx-n

2. 思路分析：

① 这道题目实际上考察的是快速幂运算，假如使用暴力破解的话会超时，其中快速幂运算中官方提供了两种解决方法，一种是使用递归来求解，另外一种使用的是for循环中进行乘方的运算，两者的思路是一样的，其中我感觉官方提供的递归代码写的很好，也比较容易理解，整个的递归模板的学习一下，每一次运算的时候指数都是以2的倍数去增加的，所以计算起来很快，递归的时间复杂度与空间复杂度都为logn

② 结合具体的例子会比较容易理解，最好使用debug调试一下

3. 代码如下：

官方递归代码：

class Solution {
    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }
}

按照官方的思路重新写了一遍代码：

class Solution {
   public double myPow(double x, long n) {
        double res = 1;
        double t = x;
        int sign = 1;
        if (n < 0) {
            sign = -1;
            n = -n;
        }
        for (long N = n; N > 0; N /= 2){
            if (N % 2 == 1){
                res = res * t;
            }
            t = t * t;
        }
        return sign == -1 ? 1 / res : res;
    }
}