50. pow(x, n)

题目来源：https://leetcode-cn.com/problems/powx-n/

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

说明:

  1. -100.0 < x < 100.0
  2. n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解法

错误解法：

#C++：

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        else if(n<0)
        {
            double total=1;
            for(int i=0;i<-n;i++)
                total *= x;
            total = 1.0/total;
            return total;
        }
        else if(n>0)
        {
            double total=1;
            for(int i=0;i<n;i++)
                total *= x;
            return total;
        }
        return 0;
    }
};

错误原因：

题目要求

-100.0 < x < 100.0 n 是 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1] 。

错误版本算法循环次数过多，导致运行超时

解决办法：

采用快速幂运算方法求解

「快速幂算法」的本质是分治算法，即「二分法角度」

方法一：快速幂 + 递归

class Solution {
public:
    double QuickMul(double x,int n)
    {
        if(n==0) return 1.0;
        double y=QuickMul(x,n/2);
        return n%2==0? y*y : y*y*x;
    }
    double myPow(double x, int n) {
        if(n==0)
            return 1;
        else if(n<0)
            return 1/QuickMul(x,n);
        else if(n>0)
            return QuickMul(x,n);
        return -1;
    }
};

方法二：快速幂 + 迭代

迭代的思路是将幂按照二进制进行拆分，如x^7 = x * x^2 * x^4；

class Solution {
public:
    double QuickMul(double x,long long n)
    {
        long long N = n;
        double res=1;
        if(N == 0)
            return 1.0;
        else
        {
            double t = x;
            while(N!=0){
                if(N & 0x01 == 1)
                {
                    res = res * t;
                }
                N = N >> 1;
                t = t * t;
            }
            return res;
        }
    }
    double myPow(double x, int n) {
        long long N = n; //1.00000 与 -2147483648 这组数据会越界，-N会出错，因此需要用long long存储
        return n>=0 ? QuickMul(x,N) : 1/QuickMul(x,-N);
    }
};

测试过程中遇到的问题：

1.00000 与 -2147483648 这组数据会越界，-N会出错，因此需要用long long存储n的数值，以避免-N出错。