程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode:Pow(x, n)

leetcode:Pow(x, n)

編輯:關於C++

一、 題目

題目說的很清楚,就是實現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);
    }
};

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved