[leetcode] 50. Pow(x, n)

题目描述

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

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000

提示：

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹-1
• n 是一个整数
• 要么 x 不为零，要么 n > 0 。
• -10⁴ <= xⁿ <= 10⁴

解题方法

递归

我们先总结规律，以示例1为例，2¹⁰怎么计算呢？

• 我们先计算2¹，结果为2；
• 我们再计算2²，结果为2¹ $\times$ 2¹ = 2 $\times$ 2 = 4；
• 我们再计算2⁴ = (2²)² = 2² $\times$ 2² = 4 $\times$ 4 = 16；
• 我们再计算2⁸ = (2⁴)² = 2⁴ $\times$ 2⁴ = 16 $\times$ 16 = 256；
• 此时2¹⁰ / 2⁸ = 2²，2² = 4，此时我们可以看出2¹⁰ = 2⁸ $\times$ 2² = 256 $\times$ 4 = 1024；

最后我们可以看出2¹⁰ = 2⁸ $\times$ 2² ，也就是2²和2⁸参与结果计算。那我们怎么知道哪些数参与结果计算呢？

我们可以看出10的二进制是1010，我们可以看出位数是1的位置参与过结果计算；即二进制10和1000，对应幂数2和8。

那么我们只需要计算二进制是1的位置，怎么计算呢？以10为幂数为例。

• 10 % 2 = 0，10的二进制个位数是0，10 / 2 = 5；
• 5 % 2 = 1，10的二进制十位数是1，5 / 2 = 2；
• 2 % 2 = 0，10的二进制百位数是0，2 / 2 = 1；
• 1 % 2 = 1，10的二进制千位数是1，1 / 2 = 0；

通过上面辗转相除的方式，我们刚好可以求出对应二进制是1的位置。

思路我们有了，那剩下就是写代码了。

java代码

public double myPow(double x, int n) {
    // 记录n的正负
    boolean flag = n > 0;
    // 由于负数范围比正数大，所以n一律转化为负数处理
    if (n > 0) {
        n = n * -1;
    }

    double result  = 1;

    while (n < 0) {
        // 余数为-1，代表当前的二进制位为1
        if(n % 2 == -1) {
            result *= x;
        }
        x *= x;
        n /= 2;
    }
    // n为负数时，结果取倒数
    return flag ? result : 1 / result;
}

复杂度分析

时间复杂度：$O(logn)$，二进制拆分需要$O(logn)$级别的时间。
空间复杂度：$O(1)$。

相似题目

[leetcode] 29. 两数相除

• 个人公众号
  
• 个人小游戏