【一刷《剑指Offer》】面试题 11：数值的整数次方

力扣对应题目链接：50. Pow(x, n) - 力扣（LeetCode）

牛客对应题目链接：数值的整数次方_牛客题霸_牛客网 (nowcoder.com)

一、《剑指Offer》内容

二、分析题目

【快速幂 + 递归】

当指数 n 为负数时，我们可以计算 x^(−n) 再取倒数得到结果，因此我们只需要考虑 n 为自然数的情况。

假设我们需要计算 x^64，可以按照下面这个计算顺序：

从 x 开始，每次直接把上一次的结果进行平方，计算 6 次就可以得到 x^64 的值，而不需要对 x 乘 63 次 x。

下面再举一个奇数的例子，x^77 可以按照下面这个计算顺序：

在 这些步骤中，我们直接把上一次的结果进行平方，而在 这些步骤中，我们把上一次的结果进行平方后，还要额外乘一个 x。

由于每次递归都会使得指数减少一半，因此递归的层数为 O(log⁡N)，算法可以在很快的时间内得到结果。

三、代码

//力扣AC代码
class Solution {
public:
    double pow(double x, long long n)
    {
        if(n==0) return 1.0;
        double k=pow(x, n/2);
        if(n%2==0) return k*k;
        else return x*k*k;
    }
    double myPow(double x, int n) {
        if(n<0) return 1.0/pow(x, (long long)n);
        else return pow(x, n);
    }
};
 
//牛客AC代码
class Solution {
public:
    double myPow(double x, int n)
    {
        if(n==0) return 1.0;
        double k=myPow(x, n/2);
        if(n%2==0) return k*k;
        else return x*k*k;
    }
    double Power(double base, int exponent) {
        if(exponent<0) return 1.0/myPow(base, exponent);
        else return myPow(base, exponent);
    }
};