Pow(x, n)

Implement pow(x, n).

解题

直接顺序求解，时间复杂度O(N)

public class Solution {    /**     * @param x the base number     * @param n the power number     * @return the result     */    public double myPow(double x, int n) {        // Write your code here        if(x == 0)            return 0;        if(n == 0)            return 1.0;        if( n<0)            return 1.0/(myPow(x,-n));        double res = x;        while(n>1){            res*=x;            n--;        }        return res;    }}

 

class Solution:    # @param {double} x the base number    # @param {int} n the power number    # @return {double} the result    def myPow(self, x, n):        # Write your code here        return x**n

 递归方式

对n时候奇数还是偶数的时候进行讨论

public class Solution {    /**     * @param x the base number     * @param n the power number     * @return the result     */    public double myPow(double x, int n) {        // Write your code here        if(x == 0)            return 0;        if(n == 0)            return 1.0;        if( n<0)            return 1.0/(myPow(x,-n));        double res = myPow(x,n/2);                if(n%2==1){            res = res * res *x;        }else{            res = res * res;        }         return res;    }}

递归程序中间需要比较多的栈，容易发生内存溢出的情况

 改写成循环的形式，效果更好，参考于libsvm源码

public class Solution {    public double myPow(double x, int n) {        if(n==0)            return 1.0;        if(x==1)            return 1.0;        if(n<0){            if (n == Integer.MIN_VALUE)                return myPow(x, n+1)/x;            else                 return 1.0/myPow(x, -n);        }                            double tmp = x;        double ret = 1.0;        for(int time = n;time>0;time/=2){            if(time%2==1)                ret *= tmp;            tmp*=tmp;        }        return ret;    }}

上面程序对n是最小值得时候进行了处理，LeetCode测试样例有 2 ，Integer.MIN_VALUE ,上面单独处理，可以通过