leetcode:Pow(x, n)

一、 題目

題目說的很清楚，就是實現pow()函數。

二、 分析

看到題目後，首先想到一個個算，心想應該會超時，果不其然。想到了二分法，這樣減少了不少的運算。沒有什麼難度的思路。

雖然思路是二分，但是又有不同的實現形式。下面使用三種》

while實現：

class Solution {
public:
    double pow(double x, int n) {
        if(n == 0)
        	return 1.0;
        if(n == 1)
        	return x;
        int nflag = abs(n);
        int nflag2 = nflag;

        double xflag = abs(x);
        double xflag2 = xflag;

        int s = 1;
        while(nflag / 2 > 0){
        	xflag2 = xflag2 * xflag2;
        	nflag = nflag / 2;
        	s = s * 2;
        }
        xflag2 = xflag2 * pow(xflag, nflag2 - s);

        if(x < 0 && n % 2 == 1)
        	xflag2 = -xflag2;
        if(n < 0)
        	xflag2 = 1 / xflag2;
        return xflag2;
    }
};

遞歸實現一：

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

遞歸實現二：

class Solution {
public:
    double pow(double x, int n) {
    	if(n == 0)
    		return 1.0;
    	double res = pow(x,n/2);
    	if(n % 2 != 0){
    		if(n > 0)
    			return (res * res * x);
    		else
    			return (res / x * res);
    	}
    	return (res * res);
    }
};