码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居西雅图。


Pow(x, n)

指数计算应该是递归程序设计的入门级题目,但是在一场面试中写一个bug-free的代码还是需要多多注意边界条件。首先是底数的正负会影响结果,其次是指数的正负,也会影响结果。因为函数原型是pow(int x, int n),所以指数一定是整数。题目的一个简单思路是使用一个循环计算n遍x的乘积,但是这样的计算复杂度太高。如果我们想计算pow(x,16),我们需要做15次乘法,这样的开销很大。使用分治法换一个角度考虑,pow(x,16)其实可以分成两个pow(x,8)的乘积,同样的,pow(x,8)可以分成两个pow(x,4)的乘积,这样计算下去,只需要计算4次乘法就可以完成。如果pow(x,15)该怎么算?其实只要计算两个pow(x,7)的乘积再乘以x即可。在实现的时候有一个细节需要注意。当写递归的代码时,不要使用return pow(x,n/2)*pow(x,n/2)这样的语句,因为这样会造成重复计算pow(x,n/2)两次,增加运算的复杂度。使用一个变量保存pow(x,n/2)的结果才是正解。此题同样是Leetcode OJ上的题目,下面是其Java实现。

public class Solution {

	/**
	 * Implement pow(x, n).
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(new Solution().pow(2.0,10));

	}
	
	public double pow(double x, int n) {
		// Start typing your Java solution below
		// DO NOT write main() function
		boolean neg = false;
		
		if((x == 0 && n == 0) || (x == 1)){
			return 1;
		}
		else if(x == 0){
			return 0;
		}
		else if (x > 0){
			neg = false;
		}
		else{
			if(neg){
				return pow(x*(-1),n);
			}
			else{
				return (-1)* pow(x*(-1),n);
			}
		}	
		
		if(n == 0){
			return 1;
		}
		else if(n == 1){
			return x;
		}
		else if (n > 0){
			if( n % 2 == 0){
				double temp = pow(x, n/2);
				return temp * temp;
			}
			else{
				double temp = pow(x, (n-1)/2);
				return temp * temp * x;
			}
		}
		else{
			double temp = pow(x, n*(-1));
			return 1.0 / temp;
		}	
	}
}
最近的文章

但愿你们一切都好

四川有一次大地震,完全不能相信。拿起电话拨通那些已经一年多没有联系的号码,感觉真的好亲切。 正因为五年前有过类似的经历,才能深刻的体会到当时的那种恐惧和无助。但愿你们一切都好。…

Life继续阅读
更早的文章

Valid Parentheses

括号题目是一类经典的算法题目,有很多变形。这类题目乍一看上去没有什么思路,但是实质上就是最近成对括号的匹配问题。常用的方法有记录括号数目和使用栈两种方式。 合法括号的判断问题是指在一串由()[]和{}…

Technical, Career继续阅读
comments powered by Disqus