剑指offer最优解Java版-数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

第一种方案：传统公式求解

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

复杂度分析：

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

第二种方案

方案的要点：

1. 全面考察指数的正负、底数是否为零等情况。
2. 写出指数的二进制表达，例如13表达为二进制1101。
3. 举例:10^1101 = 10^0001 * 10^0100 * 10^1000。
4. 通过&1和>>1来逐位读取1101，为1时将该位代表的乘数累乘到最终结果。

class Solution {
    public double Power(double base, int n) {
        double res = 1, curr = base;
        int exponent;
        if (n > 0) {
            exponent = n;
        } else if (n < 0) {
            if (base == 0)
                throw new RuntimeException("分母不能为0");
            exponent = -n;
        } else {// n==0
            return 1;// 0的0次方
        }
        while (exponent != 0) {
            if ((exponent & 1) == 1)
                res *= curr;
            curr *= curr;// 翻倍
            exponent >>= 1;// 右移一位
        }
        return n >= 0 ? res : (1 / res);
    }
}

复杂度分析：

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

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我