Implement pow(x, n).
Solution1：递归实现
思路： 2^7 = (half=2^3) ^2 * 2，分成相同的两半23，只计算其中一半即可，而不用2来乘七次，继续对23递归相同操作
实现用递归
Time Complexity: O(logN) Space Complexity: O(logN) 递归缓存
Solution2：Iterative实现
思路： x ^ 5, 5=101, 低到高第一位是1, result *= x, 第二位是0， nothing for x^2，第三位是1，result *= x^4，而x ^ n是累积乘自身得出的 x^4 = (x^2) ^ 2
实现用递归
Time Complexity: O(logN) Space Complexity: O(1)
Solution1 Code：
class Solution1a {
// 2^7 = (half=2^3)^2 * 2
// 2^6 = (half=2^3)^2
public double myPow(double x, int n) {
if(n < 0) {
n = -n;
x = 1 / x;
}
return helper(x, n);
}
private double helper(double x, int n) {
if(n == 0) return 1;
double half = helper(x, n / 2);
if(n % 2 == 0)
return half * half;
else
return x * half * half;
}
}
public class Solution1b{
public double pow(double x, int n) {
if(n == 0)
return 1;
if(n<0){
n = -n;
x = 1/x;
}
return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
}
}
Solution2 Code：
class Solution2 {
double myPow(double x, int n) {
if(n == 0) return 1;
if(n < 0) {
n = -n;
x = 1/x;
}
double ans = 1;
while(n > 0){
if(n & 1) ans *= x;
x *= x;
n >>= 1;
}
return ans;
}
}
