【LeetCode】【剑指offer】【数值的整数次方】

剑指 Offer 16. 数值的整数次方

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

如果是采用循环幂的方式容易超时

class Solution {
public:
    double myPow(double x, int n) {
        double result;
        result=1;
        if(x==1)
        {
            return 1;
        }
        if(n<0)
        {
            int y=0-n;
            while(y--)
            {
                result*=x;
            }
            result=1/result;
            return result;
        }
        else
        {
            while(n--)
            {
                result*=x;
            }
            return result;
        }
    }
};

我们可以使用快速幂的方式，也就是如果幂是奇数的话，就将这个单独的奇数乘给结果，让我们的幂保持偶数的状态，然后让幂整除2，然后底数平方，并不断迭代。

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

但是上面的算法效率还是太低，我们可以进一步提升，采用递归的写法

class Solution {
public:
    double myPow(double x, long long n) {
        return n>0 ?myquickpow(x,n):1.0/myquickpow(x,-n);
    }
    double myquickpow(double x,long long m){
        if(x==1 ||m==0)
        {
            return 1;
        }
//递归调用自身
        double result =myquickpow(x,m/2);
//如果是奇数的话就需要多乘一个底数
//如果是偶数的话就直接平方。
        return (m%2==1) ? result*result*x :result*result;
    }
};