Pow X N

50. Pow(x, n)

分析

长整型 LL 定义：long long 类型用于处理 n = INT_MIN 的情况，因为 abs(INT_MIN) 会溢出 int 类型
判断 n 是否为负数：如果 n 是负数，最后需要返回 1 / res
快速幂的实现：通过右移 k（即 k >>= 1）将 n 每次除以 2，并根据 k 是否为奇数来决定是否将当前的 x 乘到结果中
计算 x^n：
- 如果 k 的最低位是 1（即 k & 1），则当前的 x 需要乘到结果中
- 每次将 x 平方，即 x = x * x，这相当于将指数减少了一半
负指数情况：如果 n 是负数，返回 1 / res，否则返回计算结果 res

时间复杂度

时间复杂度 O(logn)，每次将 n 减半，通过二进制方式快速计算

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    double myPow(double x, int n)
    {
        using LL = long long;  // 使用 long long 类型来处理 n = INT_MIN 的特殊情况
        bool is_minus = (n < 0);  // 判断 n 是否为负数
        double res = 1;

        // 使用绝对值的 n 进行计算，避免负数的影响
        for (LL k = std::abs(LL(n)); k; k >>= 1)  // 快速幂算法：k 是二进制表示
        {
            if (k & 1)  // 如果 k 的最低位是 1
                res *= x;  // 将当前的 x 乘到结果上
            x *= x;  // x 自身平方
        }

        if (is_minus)  // 如果 n 是负数，返回 1 / res
            return 1 / res;
        return res;
    }
};