首页 > 其他 > 详细

Leetcode Pow(x,n)

时间:2014-07-07 14:59:10      阅读:305      评论:0      收藏:0      [点我收藏+]

Implement pow(xn).

明显的二分解决

由于n不可能总是偶数,

  如果n是正奇数,那么n个x的乘积等于两部分的乘积再乘以x

  如果n是负奇数,那么n个x的乘积等于两部分乘积再乘以1/x

class Solution {
public:
    double pow(double x, int n) {
        if( n == 0) return 1.0;
        double half = pow(x,n/2);
        if(n%2 == 0) return half*half;
        else if(n > 0 ) return half*half*x;
        else return half*half/x;
    }
};

也可以把负数n直接转换成正数再计算,递归方法:

class Solution {
public:
    double pow(double x, int n) {
        if( n == 0) return 1.0;
        if( n == 1) return x;
        int exp =abs(n);
        double result = (exp%2 == 0) ? pow(x*x,exp/2):pow(x*x,exp/2)*x;
        return n < 0 ?1.0/result : result;
    }
};

Leetcode Pow(x,n),布布扣,bubuko.com

Leetcode Pow(x,n)

原文:http://www.cnblogs.com/xiongqiangcs/p/3815256.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!