题⽬描述

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

示例1:
输⼊：2.00000,3
返回值：8.00000

示例2:
输⼊：2.10000,3
返回值：9.26100

思路及解答

暴力求解

如果使⽤暴⼒解答，那么就是不断相乘，对于负数⽽⾔，则是相除，并且符号取反。

public class Solution {
	public double Power(double base, int exponent) {
		if (exponent 

拆解递归

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

对于xⁿ，可以分解为：

• 如果n为偶数：xⁿ = xⁿ/² * xⁿ/²
• 如果n为奇数：xⁿ = x * xⁿ/² * xⁿ/²

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

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 

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

迭代快速幂算法

将指数表示为二进制形式，通过位运算减少乘法次数。例如，计算3¹³（1101₂）可以分解为3⁸ * 3⁴ * 3¹。

public double power(double base, int exponent) {
    if (exponent == 0) {
        // 指数为0则直接返回1
        return 1;
    }
    
    if (base == 0) {
        //底数为0直接返回0
        return 0;
    }
    
    long exp = Math.abs((long)exponent);
    double result = 1.0;
    
    while (exp > 0) {
        if ((exp & 1) == 1) { // 当前二进制位为1
            result *= base;
        }
        base *= base; // 平方
        exp >>= 1; // 右移一位
    }
    
    return exponent > 0 ? result : 1.0 / result;
}

Java标准库

public double power(double base, int exponent) {
    if (exponent == 0) {
        // 指数为0则直接返回1
        return 1;
    }
    
    if (base == 0) {
        //底数为0直接返回0
        return 0;
    }
    
    return Math.pow(base, exponent);
}

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top