首页 > 代码库 > LeetCode: Pow(x, n) [049]

LeetCode: Pow(x, n) [049]

2024-07-05 21:13:15   225人阅读

【题目】


Implement pow(x, n).



【题意】

实现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;
    }
};


联系
我们