Implement pow(x, n).
eg. 2^2 = 2^1 * 2^1 = (2^0 * 2^0 * 2) * (2^0 * 2^0 * 2) = (1 * 1 * 2) * (1 * 1 * 2) = 4
eg. 2^3 = 2^1 * 2^1 * 2 = (2^0 * 2^0 * 2) * (2^0 * 2^0 * 2) * 2 = (1 * 1 * 2) * (1 * 1 * 2) * 2 = 8
注意：负数的int的取值范围为-2^31~2^31-1,如果直接使用-n会导致栈溢出
approach1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public double myPow(double x, int n) {
return pow(x, n);
}
private static double pow(double x,long n) {
if (n == 0) {
return 1;
}
if (n < 0) {
return 1 / pow(x, -n);
}
if (n % 2 == 1) {
return x * pow(x * x, n / 2);
}
return pow(x * x, n / 2);
}
}
|
time: O(logn)
space: O(logn)
approach2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static double myPow2(double x, int n) {
if (n == 0) return 1;
double res = 1;
long abs = Math.abs((long)n);
while (abs > 0) {
if (abs % 2 != 0) {
res *= x;
}
x *= x;
abs /= 2;
}
if (n < 0) {
return 1.0 / res;
}
return res;
}
|
time: O(logn)
space: O(1)