50. Pow(x, n)
實現(xiàn) pow(x, n) ，即計算 x 的 n 次冪函數(shù)钳降。
示例 1:
輸入: 2.00000, 10
輸出: 1024.00000
示例 2:
輸入: 2.10000, 3
輸出: 9.26100
示例 3:
輸入: 2.00000, -2
輸出: 0.25000
解釋: 2-2 = 1/22 = 1/4 = 0.25
暴力法
時間復雜度O(n)
public double myPow(double x, int n) {
if(n < 0){
n = -n;
x = 1/x;
}
double result = 1;
for (int i = 0; i < n; i++) {
result *= x;
}
return result;
}
分治
/**
* 2 分治法：使用遞歸實現(xiàn)
* template：
* 1. terminator
* 2. process(split your big problems)
* 3. drill down(subproblems),merge(subresult)
* 4. reverse states
*/
/**
* pow(x,n):
* subproblem : subresult = pow(x,n/2)
* merge:
* if n % 2 = 1 //odd
* result = subresult * subresult * x
* else //even
* result = subresult * subresult
*/
public double myPow(double x, int n) {
if (n < 0) {
n = -n;
x = 1 / x;
}
return fastPow(x, n);
}
double fastPow(double x, int n) {
//1. terminator
if (n == 0) {
return 1.0;
}
// 2. process(split your big problems)
// n = n / 2;
//3. drill down(subproblems),merge(subresult)
double half = fastPow(x, n / 2);
return n % 2 == 0 ? half * half : half * half * x;
// 4. reverse states
}
