26
05/2015
[LeetCode] Pow(x, n)
Pow(x, n)
Implement pow(x, n).
解题思路：
这里n是整数，注意可能是负数，因此需要先将其转化成正数。若直接用循环的方法做，会产生超时错误。我们可以这么做。比如求2^6，我们需要求2^(2*3)=4^3=4*4^2，这样时间复杂度为O(logn)。
注意几个特殊的情况，当n==1时，返回x本身，当n==0时，返回1，当n为偶数时，返回myPow(x*x, n/2)，当n为奇数时，返回x*myPow(x*x, n/2)
class Solution {
public:
double myPow(double x, int n) {
if(n<0){
n=-n;
x=1/x;
}
if(n==1){
return x;
}
if(n==0){
return 1;
}
double temp=1;
if(n%2==1){
temp=x;
}
return temp * myPow(x*x, n/2);
}
};update in 2015.05.27
后来分析了一下，上述代码中，n==1的分支其实可以不必的。因此，代码就变成了：
class Solution {
public:
double myPow(double x, int n) {
if(n<0){
n=-n;
x=1/x;
}
if(n==0){
return 1;
}
double temp=1;
if(n%2==1){
temp=x;
}
return temp * myPow(x*x, n/2);
}
};二次刷题（2015-08-19）
class Solution {
public:
double myPow(double x, int n) {
if(n<0){
x = 1/x;
n = -n;
}
if(n == 1){
return x;
}
if(n == 0){
return 1;
}
if(n&1){
return x*myPow(x*x, n>>1);
}else{
return myPow(x*x, n>>1);
}
}
};转载请注明：康瑞部落 » [LeetCode] Pow(x, n)
0 条评论