50. Pow(x, n)

难度：中等

题目

实现 pow(x, n)，即计算 x 的 n 次幂函数。

示例 1：

输入: 2.00000, 10
输出: 1024.00000

示例 2：

输入: 2.10000, 3
输出: 9.26100

示例 3：

输入: 2.00000, -2
输出: 0.25000
解释: 2^(-2) = (1/2)^2 = 1/4 = 0.25

说明：

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是\([−2^{31}, 2^{31} − 1]\)。

Reference

题解

基本思路： 利用快速幂的思路，存储次数为2的整数幂的计算结果，然后用这些结果相乘得到输出结果。注意指数为负数的情况。当指数为-2147483648时不能取负，此时可以先加一再取负，最后除以底数。

代码如下：

double myPow(double x, int n)
{
    if (n < 0)
        return 1 / myPow(x, -(n + 1)) / x;
    double cache[32] = {0}, ret = 1;
    int i = 0;
    cache[0] = x;
    while (n)
    {
        if (n & 1)
            ret *= cache[i];
        n >>= 1;
        i++;
        cache[i] = cache[i - 1] * cache[i - 1];
    }
    return ret;
}

评论