Implement pow(x, n).
Code from http://www.programcreek.com/2012/12/leetcode-powx-n/
Recursive Version
http://www.programcreek.com/2012/12/leetcode-powx-n/
区别就是 面试官小姐姐一直在问 如果不能用这个怎么办 如果不能那样怎么办。。。。。。
1. 因为⾯面试官把return type写成了了int，竟然忘记检查power是不不是负数，
⾯面试官给了了⼀一个负数的test case，argue了了⼀一下这种情况就返回0⾏行行不不⾏行行，
⾯面试官说⾏行行之后添了了⼀一⾏行行code。
2. 简化版，保证x和n都是正整数。
3. power of n 变种， 限制使⽤用 + - * / %
4. iterative & recursive两种⽅方法，实际中哪个运⾏行行较快
- nest myPow
double myPow(double x, int n) {
if(n<0) return 1/x * myPow(1/x, -(n+1));
if(n==0) return 1;
if(n==2) return x*x;
if(n%2==0) return myPow( myPow(x, n/2), 2);
else return x*myPow( myPow(x, n/2), 2);
}
- double myPow
double myPow(double x, int n) {
if(n==0) return 1;
double t = myPow(x,n/2);
if(n%2) return n<0 ? 1/x*t*t : x*t*t;
else return t*t;
}
- double x
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0){
n = -n;
x = 1/x;
}
return n%2==0 ? myPow(x*x, n/2) : x*myPow(x*x, n/2);
}
- iterative one
double myPow(double x, int n) {
if(n==0) return 1;
if(n<0) {
n = -n;
x = 1/x;
}
double ans = 1;
while(n>0){
if(n&1) ans *= x;
x *= x;
n >>= 1;
}
return ans;
}
public double MyPow(double x, int n) {
double ans = 1;
long absN = Math.Abs((long)n);
while(absN > 0) {
if((absN&1)==1) ans *= x;
absN >>= 1;
x *= x;
}
return n < 0 ? 1/ans : ans;
}
X. bit
double pow(double x, int n) {
if(n<0){
x = 1.0/x;
n = -n;
}
int unsigned m = n;
double tbl[32] = {0};
double result = 1;
tbl[0] = x;
for(int i=1;i<32;i++){
tbl[i] = tbl[i-1]*tbl[i-1];
}
for(int i=0;i<32;i++){
if( m & (0x1<<i) )
result *= tbl[i];
}
return result;
}
};
In bit format and for a unsigned number, the number is represented as
k0*2^0 + k1*2^1 + ... +k31*2^31. Therefore, once we know the pow(x,2^0), pow(x,2^1), ..., pow(x,2^31), we can get pow(x,n). And pow(x,2^m) can be constructed easily as pow(x,2^m) = pow(x,2^(m-1)*pow(x,2^(m-1).Code from http://www.programcreek.com/2012/12/leetcode-powx-n/
public class Pow {
public double pow(double x, int n) {
// Handling special cases
if (n == 0)
return 1;
if (x == 0 || x == 1)
return x;
if (x == -1) {
if ((n & 1) == 1)
return -1;
else
return 1;
}
double result = 1;
// Handling the case when n is negative
// pow(x,n) would normally become pow(1/x,-n)
if (n < 0) {
x = 1.0 / x;
// Handle this case before n=-n; otherwise n would still be negative after n=-n
if (n == Integer.MIN_VALUE) {
result *= x;
n++;
}
n = -n;
}
// Understand pow(x,n) in terms of binary representation of n: n_k, ..., n_1, n_0
// n_i = 1 : multiply x 2^i times
while (n != 0) {
if ((n & 1) == 1)
result *= x;
x *= x;
n >>= 1;
}
return result;
}
http://yucoding.blogspot.com/2013/03/leetcode-question-74-powxn.html double pow(double x, int n) { if (x==0){ if (n==0){return 1;} else {return 0;} } if (n==0){ return 1; } bool pos=true; if (n<0){ pos = false; n=abs(n); } double np=x; double res=1; while (n>0){ if (n%2==1){ res = res * np; } np=np*np; n=n/2; } return pos? res:1/res; }http://www.programcreek.com/2012/12/leetcode-powx-n/
public double power(double x, int n) { if (n == 0) return 1; double v = power(x, n / 2); if (n % 2 == 0) { return v * v; } else { return v * v * x; } } public double pow(double x, int n) { if (n < 0) { // to-do handle: n is min_value return 1 / power(x, -n); } else { return power(x, n); } } |
区别就是 面试官小姐姐一直在问 如果不能用这个怎么办 如果不能那样怎么办。。。。。。
1. 因为⾯面试官把return type写成了了int，竟然忘记检查power是不不是负数，
⾯面试官给了了⼀一个负数的test case，argue了了⼀一下这种情况就返回0⾏行行不不⾏行行，
⾯面试官说⾏行行之后添了了⼀一⾏行行code。
2. 简化版，保证x和n都是正整数。
3. power of n 变种， 限制使⽤用 + - * / %
4. iterative & recursive两种⽅方法，实际中哪个运⾏行行较快
