leetcode_07 :50.Pow(x,n)

实现 [pow(x, n)]，即计算 x 的 n 次幂函数。
说明:

-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−2^31, 2^(31 − 1)] 。
思路1(最笨方法)：
如果x>0直接for循环计算.
x<0的时候,取倒数
代码如下

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

};

但是会出现运行超时，所以这个方法不可行。
方法2：
可以看作是这样的方式计算得来的。
举例：





所以需要6次就可以实现
需要倒着算来看需要多少次，若是奇数，则需要多乘一个x，可以用temp_n=n/2是否等于0来判断是否结束，若temp_n%2！=0,需要多乘一个x.

class Solution {
public:
    double myPow(double x, int n) {
       int i=n;
       if(n<0)
            i=-n;
        double result=1;
        for(i;i!=0;i/=2)
        {
            if(i%2!=0)
                result*=x;
            x*=x;
        }
        return n<0? 1/result: result;
    }   

};

这次依然没有成功，当n=-2147483648时，取反的时候会溢出。
因为int型取值范围是[]，不能直接取反，需要借助递归。

class Solution {
public:
    double pow(double x, long long n)
    {
        int i=n;
        double result=1;
        for(i;i!=0;i/=2)
        {
            if(i%2!=0)
                result*=x;
            x*=x;
        }
        return result;
    }
    double myPow(double x, int n) {
        long long n_1=n;
        return n<0? 1/pow(x,-n_1):pow(x,n);

    }   

};

答案无敌思路，用二进制中的1来进行计算。

class Solution {
public:
    double quickMul(double x, long long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    double myPow(double x, int n) {
        long long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }
};