Pow(x, n)

Implement pow(x, n).

数据结构书上的原题,也是一个经典题.直接上手写了,但第一次没过.因为没考虑到n为负数的情况.第二次AC.

时间复杂度O(logn)

C++:

class Solution {
public:
    double pow(double x, int n){
        return n<0?1/_pow(x,-n):_pow(x,n);
    }
    
    double _pow(double x, int n) {
        if (n == 0){
            return 1;
        }
        else if(n == 1){
            return x;
        }
        else{
                double y = pow(x, n / 2);
                if(n % 2 == 0){
                    return y * y;
                }
                else{
                    return y * y * x;
                }
            }
        }
};