Implement pow(x, n).
A:
----------4th pass---------Iterative way ------------
public class Solution {
public double pow(double x, int n) {
if(n<0)
return 1/(x*pow(x,-(n+1)));
double result = 1;
while(n!=0){
if(n%2 ==1)
result *= x;
x = x*x;
n = n>>1;
}
return result;
}
}
Mistakes:
1: 第一次实现的时候,,没有考虑效率。 就直接n 个x连乘了。
2: 当建立ArrayList 的时候, while (al.get(al.size() - 1) * 2 <n) { 但是这里,应该是 <= n 的
3:
Learned:
1:计算以2为底的log函数
-----------------3rd pass -------------------直接来计算----------
Error:
1: 刚开始,分开考虑 n 的正负号。 但真因为这样, 负数转正数会有溢出的情况。
public double pow(double x, int n) {
if(n==0)
return 1;
if(n<0)
return 1/powPos(x,-n);
// now n>0
return powPos(x,n);
}
因此,上面是不对的。
2: double powPos()的base case应该是 n == 0;
教训阿, 还是分情况简单好记。 否则的话,会容易惹出不必要的错误。 而且既然自己不太熟悉 bit 操作。 那就在面试的时候尽量避免。
class Solution { public: double myPow(double x, int n) { if(n<0) return 1 /(x* myPow(x, -(n+1))); // n -> -n can have overflow if n<0 if(n==0) return 1; double res = n&1 ? x : 1;double half = myPow(x, n/2); return res * half * half; } };
最终改成了: ----------- 教训: 当int 负数变正数的时候,一定要检查是否有溢出。 (或者我们就一直用负数来搞。
public class Solution {
public double pow(double x, int n) {
return pow2(x,n);
}
private double pow2(double x, long n){
if(n==0)
return 1;
if(n<0)
return 1/pow2(x,-n);
double b = pow2(x,n/2);
if(n%2==0)
return b*b;
else
return b*b*x;
}
}
--------------------都当作负数来搞------------------------------------
public class Solution {
public double pow(double x, int n) {
if(n==0)
return 1;
if(n==-1)
return 1/x;
if(n>0)
return 1/pow(x,-n);
double b = pow(x,n/2);
if(n%2==0)
return b*b;
else
return b*b*1/x;
}
}
No comments:
Post a Comment