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

本文主要是介绍【一刷《剑指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);}
};

这篇关于【一刷《剑指Offer》】面试题 11：数值的整数次方的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---