现在的位置: 首页 > 综合 > 正文

LeetCode OJ –问题与解答 pow(x,n)

2014年04月05日 ⁄ 综合 ⁄ 共 895字 ⁄ 字号 评论关闭

题目


Implement pow(xn).

完成函数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不能直接用“==”。”

这点是我一开始没有注意到的,虽然通过了,但是逻辑上面没有符合上面的正确规定。

抱歉!评论已关闭.