Implement pow(x, n).
Hide Company Tags
LinkedIn Google Bloomberg Facebook
Hide Tags
Binary Search Math
Hide Similar Problems
(E) Sqrt(x) (M) Super Pow
** 解題思路 **
這道題有幾種解題思路。 主要思想是用二分查找來做蛋褥， 需要區(qū)分n < 0, n %2 == 1 or n % 2 == 0 幾種情況虱歪。 例如友绝，
2 ^ 5 = 2 * myPow( 2 * 2 , 5/2)
2 ^ 4 = myPow(2 * 2 , 4/ 2)
當(dāng)然如果用暴力做法 return x * x * x ... * x (n 個x 相乘） 會造成leetcode oj報(bào)錯。
下面是五種寫法语御，僅供參考梯醒。
- 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;
}
- bit operation
see this solution
If you have other ideas, please leave it below. Thanks.
