LeetCode-Pow(x, n)

Posted by mapoto4 on 2017-07-20

题目

Implement pow(x, n).

解题思路

首先考虑所有的特殊情况:分母为零,分子为零,分子为负数

通过分治法,将n = n / 2划分,直到n=1

如果n % 2 == 0x ^ n = ( x * x ) ^ ( n / 2 )
否则x ^ n = x * ( x * x ) ^ ( n / 2 )

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static double myPow(double x, int n) {
if (x == 0) {
return 0;
}
if (n == 1) {
return x;
}
if (n == 0) {
return 1;
}
if (n < 0) {
x = 1 / x;
n = -1 * n;
}
double sum = (n % 2 == 0) ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
if (sum >= 2147483647 || sum <= -2147483648)
return 0;
else
return sum;
}