题目描述

给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent。求 base 的exponent次方。保证 base 和 exponent 不同时为 0。

示例1:

输入：
2.00000,3

返回值：
8.00000

示例2:

输入：
2.10000,3

返回值：
9.26100

思路 & 解答

如果使用暴力解答，那么就是不断相乘，对于负数而言，则是相除，并且符号取反。

Java 实现如下：

public class Solution {
    public double Power(double b, int n) {
        if (n < 0) {
            b = 1 / b;
            n = -n;
        }
        double result = 1.0;
        for (int i = 0; i < n; ++i) {
            result *= b;
        }
        return result;
    }
}

C++ 代码如下：

class Solution {
public:
    double Power(double base, int exponent) {
        if (exponent < 0) {
            base = 1 / base;
            exponent = -exponent;
        }
        double result = 1.0;
        for (int i = 0; i < exponent; ++i) {
            result *= base;
        }
        return result;
    }
};

题目中的 double 类型应该不能拆解，但是 int 类型的整数 exponet 我们可以做点文章，我们平时求次方的时候，假设有个 x 的 4 次方，我们通常是求出一个 x 的平方数 x^2，然后两个 x^2 相乘就可以得出 x^4。

这里思路也一样，使用递归，同时考虑边界条件。 如果指数是负数，则先取反，最后取结果的倒数即可。

$$ Power(base,ex)=\begin{cases} base*Power(base,ex-1),ex取余2=1 \ Power(base,ex/2)*Power(base,ex/2),ex取余2=0\ \end{cases} $$

Java 代码如下：

    public double Power(double base, int exponent) {
        if (exponent == 0) {
            // 指数为0则直接返回1
            return 1;
        }
        if (base == 0) {
            //底数为0直接返回0
            return 0;
        }
        // 判断指数是否为负数
        boolean isNegative = false;
        if (exponent < 1) {
            exponent = -exponent;
            isNegative = true;
        }
        double result;
        if (exponent % 2 == 1) {
            result = base * Power(base, exponent - 1);
        } else {
            double temp = Power(base, exponent / 2);
            result = temp * temp;
        }
        return isNegative ? (1.0 / result) : result;
    }

C++代码如下:

class Solution {
public:
    double Power(double base, int exponent) {
        if (exponent == 0) {
            // 指数为0则直接返回1
            return 1;
        }
        if (base == 0) {
            //底数为0直接返回0
            return 0;
        }
        // 判断指数是否为负数
        bool isNegative = false;
        if (exponent < 1) {
            exponent = -exponent;
            isNegative = true;
        }
        double result;
        if (exponent % 2 == 1) {
            result = base * Power(base, exponent - 1);
        } else {
            double temp = Power(base, exponent / 2);
            result = temp * temp;
        }
        return isNegative ? (1.0 / result) : result;
    }
};

时间复杂度：O(logn)，每次计算后规模缩小一半 空间复杂度：O(logn)，递归的时候，栈需要用到变量