首页 > 其他 > 详细

LeetCode: Pow(x, n) [049]

时间:2014-05-26 04:37:24      阅读:314      评论:0      收藏:0      [点我收藏+]

【题目】


Implement pow(xn).



【题意】

实现pow(x, n)


【思路】

       

最直接的思路是用一个循环,乘n次的x。
当n的值较小的时候还好,当n非常大时,时间成本就非常高。加入n=INT_MAX, 也就是21亿多次循环,你可以试想一下。
在这种情况下,我们需要快速的乘完n个x,采用尝试贪心的方法,即滚雪球方式的翻倍相乘
        
注意:几种特殊情况
            1. n=0;
            2. n<0;


【代码】

class Solution {
public:
    double pow(double x, int n) {
        if(x==0)return 0;   //两种特殊情况
        if(n==0)return 1;
        
        
        double result=1;
        bool isNegative= n<0?true:false;
        long long nTotal= isNegative? -1*n : n;
        long long nUsed=1;
        long long nUsedTotal=0;
        double multiply=x;
        
        while(nUsedTotal<nTotal){
            nUsed=1;
            multiply=x;
            while(nUsed*2<nTotal-nUsedTotal){
                nUsed*=2;
                multiply = multiply*multiply;
            }
            nUsedTotal+=nUsed;
            result*=multiply;
        }
        if(isNegative) return 1/result;
        return result;
    }
};


LeetCode: Pow(x, n) [049],布布扣,bubuko.com

LeetCode: Pow(x, n) [049]

原文:http://blog.csdn.net/harryhuang1990/article/details/26668929

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