Implement pow(x, n).
完成函数x^n
1 return Math.pow(x,n)肯定可以。
2 主体,考虑用迭代处理,递归需要的时间相同O(n),但是所用堆栈空间更大。
3 考虑特殊情况。x和n可能<0 =0 >0 ,分别讨论。n>0时正常;n=0时,为1;n<0时,1/x即可。x=0时为1,x>0 x<0 都没关系。
4 写出代码
public double pow(double x, int n) { if(n==0){ return 1.0; } if(x==0){ return (double)0; } if(n<0){ x=1/x; n=-n; } double temp =x; for(int i=1;i<n;i++){ x*=temp; } return x; }
5 测试之后,发觉各种情况通不过。比如x极小的情况,n极大的情况。 于是,在循环中添加了如下代码
if(Double.isInfinite(x) ||Math.abs(x)<0.0000000001){ return x; }
依然不通过,居然是x=+-1的情况。我的代码逻辑上是能够完成的,而且运行也很快。看来leetcode是希望我碰到此类情况直接处理掉,好吧,继续代码。
果然这两个一检验就通过了。。。。
好吧,但是我对我的代码不满意,太不整洁和优美了!
1 参考两个大牛的blog
http://blog.csdn.net/fightforyourdream/article/details/14218779
http://blog.csdn.net/fengbingyang/article/details/12236121
2 对于最普通的运算,他们的递归的做法表示不赞同,理由前面说过。
3 对于二分法的做法,表示可以应用,而且应该想到。然后二分法的确只能够使用递归来完成。虽然空间浪费了,但是时间上面有优势。
4 最后的方法,编程之美有说过,扫描指数的二进制码,计算为1的时候,x的幂。
5 “x取值为0时,0的正数次幂是1,而负数次幂是没有意义的;判断x是否等于0不能直接用“==”。”
这点是我一开始没有注意到的,虽然通过了,但是逻辑上面没有符合上面的正确规定。