LeetCode 0050.Pow(x, n)

实现 pow(x, n) ，即计算x的n次幂函数（即，xⁿ）。

示例 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

提示:

• − 100.0 < x < 100.0 -100.0 < x < 100.0 −100.0
• − 2 31 ≤ n ≤ 2 31 − 1 -2^{31} leq n leq 2^{31}-1 −231≤n≤231−1
• − 1 0 4 ≤ x n ≤ 1 0 4 -10^4 leq x^n leq 10^4 −104≤xn≤104

给你一个浮点数 x x x和一个整数 n n n，让你计算 x n x^n xn。

− 1 0 4 ≤ x n ≤ 1 0 4 -10^4 leq x^n leq 10^4 −104≤xn≤104，也就是说答案不会异常大。因此直接使用修改版的快速幂即可。

快速幂的介绍有很多，比如可以参考 https://letmefly.xyz/Notes/ACM/Problems/快速幂 /

但是一般的快速幂都是计算整数的整数次幂的，并且会取模。

因此我们只需要做出一些特殊修改即可：

如果 n n n是负数，就计算 1 / P o w ( x , − n ) 1 / Pow(x, -n) 1/Pow(x,−n)

注意：

一些编程语言中， n n n一定要记得转为long long，因为-INT_MIN > INT_MAX

直接套用快速幂模板并稍作修改即可。

• 时间复杂度 O ( log ⁡ n ) O(log n) O(logn)
• 空间复杂度 O ( 1 ) O(1) O(1)

class Solution {
private:
    double Pow(double x, long long n) {  // -INT_MIN > INT_MAX，因此此处需要使用long long
        double ans = 1;
        while (n) {
            if (n & 1) {
                ans *= x;
            }
            x = x * x;
            n >>= 1;
        }
        return ans;
    }
public:
    double myPow(double x, long long n) {  // 这里LeetCode中原本是int n，修改为long long可以避免-(-2147483648) = 2147483648超出INT_MAX
        return n > 0 ? Pow(x, n) : 1 / Pow(x, -n);
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/124972517