50. Pow(x, n)

快速幂

class Solution {
    public double myPow(double x, int n) {
        double res = 1;
        boolean isMinus = n < 0;
        for (long k = Math.abs((long)n); k > 0; k >>= 1) {
            if ((k & 1) == 1) {
                res *= x;
            }
            x *= x;
        }
        if (isMinus) {
            res = 1 / res;
        }
        return res;
    }
}

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