LeetCode50.Pow(x,n)

更新: 6/16/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode50. Pow(x, n)

题目意思很简单，就是求$x^n$，$-2^{31}<=n<=2^{31}-1$。

如果我们直接暴力遍历肯定是不行的，因为O(n)的时间复杂度肯定会超时，我们这里考虑快速幂+迭代：

比如要求$2^{10}$,我们可以发现他其实可以等于$2^{5^2}$,那么我们只需要求$2^5$即可，但是需要注意，接下来在求$2^5$时，他为奇数，五不能直接被二整除，所以这里我们先要给ans✖️2，然后现在只需要求$2^4$即可，然后就可以变成$2^{2^2}$即可，那么只需要求$2^2$，继续往下做就出来了。

那么代码我们就能很容易写出来了：

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if(n < 0) {
            x = 1 / x,N = -N;
        }
        double ans = 1;
        while(N) {
            if(N % 2) {
                ans *= x;
            }
            x *= x;
            N /= 2;
        }
        return ans;
    }
};