050.md

Pow(x,n)

题目

Implement pow(x, n).

example1:
Input: 2.00000, 10
Output: 1024.00000

example2:
Input: 2.10000, 3
Output: 9.26100

思路

正常写个暴力会limit time，这里主要的方法是通过递归降低乘法的次数。 n==0的时候 返回1

如果n为偶数的时 x^(n/2) * x^(n/2) = x^n

n为奇数的时候 x * x^(n/2) * x^(n/2) = x^n

n为负数的时候 (1/x)^(-n) = x^n

代码

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        if(n<0){
            return 1/x*(myPow(1/x,-(n+1)));
        }
        if(n%2==0){//偶数
            double temp = myPow(x,n/2);
            return temp*temp;
        }else{//奇数
            double temp = myPow(x,n/2);
            return x*temp*temp;
        }
    }
};

double Power(double base, int exponent) {
        if(exponent==0) return 1;
        if(exponent<0){
            return Power(1/base,-exponent);
        }
        double temp = Power(base,exponent>>1);
        if(exponent%2==0){
            return temp*temp;
        }else{
            return base*temp*temp;
        }
    }