leetcode日记（39）Pow(x,n)

话不多说，直接return pow(x,n)——

怎么可能！！

首先尝试暴力解法，循环x=x*x……时间复杂度肯定超了。

应该使用递归：

class Solution {
public:
    double P(double x,int n){
        if(n==0) return 1;
        int m=n/2;
        return n%2==0?P(x,m)*P(x,m):P(x,m)*P(x,m)*x;
    }
    double myPow(double x, int n) {
        if(n==0) return 1;
        else return n>0?P(x,n):1/P(x,-n);
    }
};

发现时间复杂度还是超了，原来是return多次调用P(x,m)，大意了，应该改为

class Solution {
public:
    double P(double x,int n){
        if(n==0) return 1;
        int m=n/2;
        double po=P(x,m);
        return n%2==0?po*po:po*po*x;
    }
    double myPow(double x, int n) {
        return n>0?P(x,n):1/P(x,-n);
    }
};

然后又发现有案例过不了：

原来是n为负数时取-n的时候int可能会超界

于是：

class Solution {
public:
    double P(double x,long long n){
        if(n==0) return 1;
        long long m=n/2;
        double po=P(x,m);
        return n%2==0?po*po:po*po*x;
    }
    double myPow(double x, int n) {
        long long m=n;
        return n>0?P(x,m):1/P(x,-m);
    }
};

改成了long long，成功通过。

后来看到另一种解法：利用二进制，比如5的二进制是101，从低位向高位看：1代表有一个多余的x，需要将结果乘以一个x，向上移一位时将x取平方，然后0代表没有多余x，可以跳过，继续上移将x平方，最后1代表有多余x，将结果乘以x……

代码：

class Solution {
public:
    double P(double x,long long n){
        double result=1;
        while(n>0){
            if(n%2==1) result*=x;
            x*=x;
            n/=2;
        }
        return result;
    }
    double myPow(double x, int n) {
        long long m=n;
        return n>=0?P(x,m):1/P(x,-m);
    }
};