Implement pow(x, n).
Solution1：遞歸實(shí)現(xiàn)
思路： 2^7 = (half=2^3) ^2 * 2云稚，分成相同的兩半23则果，只計(jì)算其中一半即可，而不用2來乘七次，繼續(xù)對(duì)23遞歸相同操作
實(shí)現(xiàn)用遞歸
Time Complexity: O(logN) Space Complexity: O(logN) 遞歸緩存
Solution2：Iterative實(shí)現(xiàn)
思路： x ^ 5, 5=101, 低到高第一位是1, result *= x, 第二位是0， nothing for x^2序调，第三位是1，result *= x^4兔簇，而x ^ n是累積乘自身得出的 x^4 = (x^2) ^ 2
實(shí)現(xiàn)用遞歸
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;
}
}
