Pow(x,n)

Pow(x, n)

Implement pow(x, n).

class Solution {
    unordered_map<int, double> pTable;
    double epsilon;
    double pow2(double x, int n){//
        if (!n) return 1.0;
        if (1 == n) return x;
        if (-1 == n) return 1/x;
        bool nFlag = false;
        if (n < 0) nFlag = true;
        if (pTable[n]) return pTable[n];
        int half = n/2;
        int res = n - half - half;
        double r1 = pow2(x, half);
        double r2 = pow2(x, res);
        double r = r1 * r1 * r2;
        if (abs(r1) < epsilon || abs(r2) < epsilon) r = 0;
        pTable[n] = r;
        return r;
    }
public:
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        epsilon = 0.0001;
        pTable.clear();
        if (!n) return 1.0;
        return pow2(x,n);
    }
};