《剑指offer刷题笔记》15、数值的整数次方【c++详细题解】

客官°小女子只卖身不卖艺 2021-07-24 22:26 266阅读 0赞

### **题目** ###

实现函数*double Power(double base, int exponent)*，求*base*的 *exponent*次方。

不得使用库函数，同时不需要考虑大数问题。

只要输出结果与答案的绝对误差不超过  1 0 − 2 10^−2 10−2即视为正确。

**注意：**

*  不会出现底数和指数同为0的情况
 *  当底数为0时，指数一定为正

**样例1**

输入：10 ，2
    
    输出：100

**样例2**

输入：10 ，-2  
    
    输出：0.01

### **思路** ###

**(模拟)**  O ( l o g n ) O(logn) O(logn)  
由于本题的指数是`int`范围，可能很大，所以需要用快速幂求解。

注意当指数是负数时，我们需要先取指数的绝对值，最后将乘积的倒数作为答案。

**时间复杂度**  
假设指数是  n n n，则一共会循环  O ( l o g n ) O(logn) O(logn) 次，所以时间复杂度是  O ( l o g n ) O(logn) O(logn)。

### **代码1** ###

class Solution { 
    public:
        double myPow(double x, int n) { 
            typedef long long LL;
            bool is_minus = n < 0;
            double res = 1;
            for (LL k = abs(LL(n)); k; k >>= 1) { 
                if (k & 1) res *= x;
                x *= x;
            }
            if (is_minus) res = 1 / res;
            return res;
        }
    };

### **代码2** ###

class Solution { 
    public:
        double Power(double x, int n) { 
            typedef long long LL;
            bool is_minus ;
            if( n < 0) is_minus = 1; //判断指数是否是负数
            LL k = abs(LL(n));
            double res = 1;
            while(k)
            { 
                if( k&1 ) res *= x;
                k >>= 1;
                x *= x;
            }
            if(is_minus) res = 1 / res;
            return res;
        }
    };