50-Pow

LeetCode 50. Pow

LeetCode

Implement pow(x, n), which calculates x raised to the power n.

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

method: 快速幂

注意n < 0的情况，要变成倒数

double pow(double x, long n) {
    double res = 1;
    while (n) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
double myPow(double x, int n) {
    long p = n; // INT_MIN会溢出
    return p < 0 ? pow(1.0/x, -p) : pow(x, p);
}

时间复杂度：$O(logn)$
空间复杂度：$O(1)$