方法一：暴力

解题思路

• 当base为0的时候，直接返回0；
• 初始化结果变量，和符号标志。后者默认为True；
• 如果exponent小于0，则令flag为False；
• 将base乘以exponent次，得到res；
• 假如exponent为负数的话，需要将1除以res；
• 返回结果res。

复杂度

• 时间复杂度为O(n)；
• 空间复杂度为O(1)。

代码

Python

class Solution:
    def Power(self , base: float, exponent: int) -> float:
        if base == 0:
            return 0
			
        res = 1.0
		
        flag = True
        if exponent < 0:
            flag = False
            exponent = abs(exponent)
			
        for i in range(1, exponent+1):
            res *= base

        if flag == False:
            res = 1/res

        return res

C++

class Solution {
public:
    double Power(double base, int exponent) {
        if(base == 0)
        {
            return 0;
        }

        double res = 1.0;
        
        bool flag = true;
        if(exponent < 0)
        {
            flag = false;
            exponent = abs(exponent);
        }

        while(exponent--)
        {
            res *= base;
        }

        if(flag == false)
        {
            res = 1/res;
        }

        return res;
    }
};

方法二：快速幂

解题思路

预备知识：

• 一个数与1进行与运算，如果结果为1则表示该数是奇数；否则为偶数。
• 一个数将位向右移一位，如果为奇数的话，则移位后的结果相当于对这个数除以2并减1；如果为偶数的话，则移位后的结果相当于这个数除以2。

思路：

• 如果指数为负数，则将底数化为分数。
• 将已乘出来的部分求次方，可以每次缩小一半要求的次方数。

复杂度

• 时间复杂度为O(logn)；
• 空间复杂度为O(1)。

代码

Python

class Solution:
 	# 快速幂
    def Pow(self, x, y):
        res = 1.0
        while y:
            if y&1:
                res *= x

            x*=x
            y = y >> 1

        return res

    def Power(self , base: float, exponent: int) -> float:
        if exponent < 0:
            base = 1/base
            exponent = -exponent

   		return self.Pow(base, exponent)

C++

class Solution {
public:
    double Pow(double base, int exponent)
    {
        double res = 1.0;

        while(exponent)
        {
            if(exponent & 1)
            {
                res *= base;
            }

            base *= base;

            exponent = exponent >> 1;
        }

        return res;
    }

    double Power(double base, int exponent)
    {
        if(exponent < 0)
        {
            base = 1/base;
            exponent = -exponent;
        }

        return Pow(base, exponent);
    }
};