首页 > 代码库 > 【LeetCode】Pow(x, n)
【LeetCode】Pow(x, n)
题目
Implement pow(x, n).
解答
直接用递归法:
//递归法("折半"递归,不要用常规的一个个乘,效率很低) 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---
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。