pow(x,n)

problem

\50. Pow(x, n)

Medium

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

1
2
3
> Input: 2.00000, 10
> Output: 1024.00000
>

Example 2:

1
2
3
> Input: 2.10000, 3
> Output: 9.26100
>

Example 3:

1
2
3
4
> Input: 2.00000, -2
> Output: 0.25000
> Explanation: 2-2 = 1/22 = 1/4 = 0.25
>

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public double myPow(double x, int n) {

long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}

double ans = 1;
double cur = x;//2
for (long i = N; i > 0; i /= 2) {
if (i % 2 == 1)
ans = ans * cur;
cur = cur * cur;
}
return ans;

}
//偷懒方法
public double myPow(double x, int n) {
return Math.pow(x, n);
}

key

其实先使用了偷懒的方法,调用Math库的pow方法,然后写过一版

1
2
3
for(long i=N;i>0;i--) {
ans=ans*cur;
}

这个会直接报超时的错误,因为的计算量会非常大,在计算(-1.00000,-2147483648)时候超时了,虽然我们可以通过判断x来避免这一个超时,但是我想到了,可以通过n/2来迅速减少相乘的次数。时间大概是8ms

perfect

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public double findPower(double x,long n){
if(n == Long.valueOf(1))
return x;
if(n % 2 == 0){
double half_pow = findPower(x,n/2);
return half_pow * half_pow;
}else{
double half_pow = findPower(x,(n-1)/2);
return half_pow * half_pow * x;
}

}
public double myPow(double x, int n) {
if( n==0 )
return 1;

long n_long = (long) n;
if( n > 0 )
return findPower(x,n);

x = 1 / x;
long n_long_abs = (long) Math.abs((long)n);
if(n_long_abs == 1)
return x;
return findPower(x,n_long_abs);
}
}