Pow(x, n)
Implement pow(x, n).
解题
直接顺序求解，时间复杂度O(N)
public class Solution {
/**
* @param x the base number
* @param n the power number
* @return the result
*/
public double myPow(double x, int n) {
// Write your code here
if(x == 0)
return 0;
if(n == 0)
return 1.0;
if( n<0)
return 1.0/(myPow(x,-n));
double res = x;
while(n>1){
res*=x;
n--;
}
return res;
}
}
Java Code
class Solution:
# @param {double} x the base number
# @param {int} n the power number
# @return {double} the result
def myPow(self, x, n):
# Write your code here
return x**n
递归方式
对n时候奇数还是偶数的时候进行讨论
public class Solution {
/**
* @param x the base number
* @param n the power number
* @return the result
*/
public double myPow(double x, int n) {
// Write your code here
if(x == 0)
return 0;
if(n == 0)
return 1.0;
if( n<0)
return 1.0/(myPow(x,-n));
double res = myPow(x,n/2);
if(n%2==1){
res = res * res *x;
}else{
res = res * res;
}
return res;
}
}
递归程序中间需要比较多的栈，容易发生内存溢出的情况
改写成循环的形式，效果更好，参考于libsvm源码
public class Solution {
public double myPow(double x, int n) {
if(n==0)
return 1.0;
if(x==1)
return 1.0;
if(n<0){
if (n == Integer.MIN_VALUE)
return myPow(x, n+1)/x;
else
return 1.0/myPow(x, -n);
}
double tmp = x;
double ret = 1.0;
for(int time = n;time>0;time/=2){
if(time%2==1)
ret *= tmp;
tmp*=tmp;
}
return ret;
}
}
上面程序对n是最小值得时候进行了处理，LeetCode测试样例有 2 ，Integer.MIN_VALUE ,上面单独处理，可以通过