題目描述
Implement pow(x, n), which calculates x raised to the power n (xn).
實現(xiàn)x的n次方操作琼腔。
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
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]
思路分析
這個題很簡單，最簡單的方法是遍歷斟叼，result*=x;偶惠，
- 但是這樣的話復雜度是O(n)。還可以靈活利用已有的結果來降低復雜度朗涩，通過遞歸忽孽，以210為例，可以將210遞歸為25 * 25谢床，依次向下求解扒腕。
- 另一方面注意到n的范圍是全部int的范圍，而int的范圍是不對稱的（[?231, 231 ? 1]）萤悴，因此需要注意負數(shù)處理時不能直接將n取-n（通過x-(n+1)*x遞歸，或者對Integer.MIN_VALUE進行特殊判斷）皆的。
- 另外注意在對奇偶進行判斷和除2時盡量使用位運算（
>> << & |）覆履，可以更好的利用計算機二進制的特性提升性能。（《劍指offer》）
代碼實現(xiàn)
public class Solution {
/**
* 304 / 304 test cases passed.
* Status: Accepted
* Runtime: 22 ms
* @param x
* @param n
* @return
*/
public double myPow(double x, int n) {
if (n < 0) {
return 1 / x * myPow(1 / x, -(n + 1));
}
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
double half = myPow(x, n >> 1);
half *= half;
if ((n & 1) == 1) {
half *= x;
}
return half;
}
}
