leetcode 50. Pow(x, n)

leetcode 50. Pow(x, n)

1.思路：快速幂算法

边算边维护
这样的时间复杂度是o(logn)

2.代码

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL;
        bool is_minus = n < 0; // 特判负数的情况
        double result = 1;

        for(LL k = abs((LL)n); k; k >>= 1){
            if(k & 1) result *= x;
            x *= x;
        }

        if(is_minus) return 1 / result;
        else return result;
    }
};