首页 > 代码库 > 【LeetCode】Pow(x, n)

【LeetCode】Pow(x, n)

题目

Implement pow(xn).

解答

直接用递归法:

//递归法("折半"递归,不要用常规的一个个乘,效率很低)
public class Solution {
    public double pow(double x, int n) {
        if(n==0)
            return 1;
        if(n==1)
            return x;
        if(n==-1)
            return 1/x;
        if(n%2==0){
            double tmp=pow(x,n>>1);     //减少子递归
            return tmp*tmp;
        }else{
            return pow(x,n-1)*x;
        }
    }
}

n比较小的时候,可以使用DP法,有效缓存DP的数组,性能会远超递归。当然递归也是有好处的,如果n很大,并且x不确定时,数组的空间会不够,这时就只能递归了。(此题DP法不能通过, pow(0.00001, 2147483647),应该是数组不能开太大

//DP法:


double pow(double x,int n){
	boolean isPositive=false;
	if(n==0)
		return 1;
	else if(n<0){
		isPositive=true;
		n*=-1;
	}
	double[] result=new double[n+1];
	result[1]=x;
	for(int i=2;i<=n;i++){
		if(i%2==0){
			result[i]=result[i/2]*result[i/2];
		}else{
			result[i]=result[i-1]*x;
		}
	}
	if(isPositive)
		return 1/result[n];
	else
		return result[n];
}


---EOF---