LeetCode 50. Pow(x, n)（二分查找）

class Solution {
public:
    double myPow(double x, int n) {
		if(n == 0) return 1.0;
		long N = n;
		if(N < 0)
		{
			x = 1/x;
			N = -N;
		}
		return POW(x, N);
    }
    double POW(double x, int N) 
    {
    	if(N == 0)	return 1.0;
    	double half = POW(x, N/2);
    	if(N%2 == 0)
    		return half*half;
    	else
    		return half*half*x;
    }
};

class Solution {//超时，0.00001，2147483647
	unordered_map<int ,double> m;
public:
    double myPow(double x, int n) {
        if(n == 0)
        	return 1.0;
        long N = n;
        if(n < 0)
        {
        	x = 1/x;
        	N = -(long)n;//INT_MIN换号后溢出
        }
        return MyP(x, N);
    }

    double MyP(double x, long N) 
    {
    	if(N == 0)
    		return 1.0;
    	if(N%2 == 0)
    	{
    		if(m.count(N))
    			return m[N];
    		double a = MyP(x, N/2)*MyP(x, N/2);
    		m[N] = a;
    		return a;
    	}
    	else
    	{
    		if(m.count(N))
    			return m[N];
    		double b = MyP(x, N/2)*MyP(x, N/2)*x;
    		m[N] = b;
    		return b;
    	}
    }
};

class Solution {
public:
    double myPow(double x, int n) {
		if(n == 0) return 1.0;
		long N = n;
		if(N < 0)
		{
			x = 1/x;
			N = -N;
		}
		double ans=1;
		double product = x;
		for(long i = N; i; i /= 2)
		{
			if(i % 2 == 1)
				ans *= product;
			product *= product;
		}
		return ans;
    }
};