LEETCODE 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/22 = 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=50

解题思路分析：

本题描述很清晰，就是自己写一个函数，求x的n次方。最暴力的解法的时间复杂度是O(n),即x乘以n次。但考虑到n会非常大，因此我们应该尝试思考使用O(logn)的时间复杂度来解题。举个例子来说明，比如求2的12次方：

1. 我们可以先求2的2次方即2*2=4。然后在求4的2次方，也就是2的4次方，即4*4=16，接下来再求16的2次方，即2的8次方，即16*16=256。在接下来，我们应该求256的2次方，即2的16次方，但此时16次方已经大于题目要求的12次方，因此此时不能再计算下去，先将已经计算好的结果进行保存，即2的8次方等于256。
2. 相对于要求的12次方还差4次方没有计算，这时回到上面1的思路，再从求2的2次方开始，即2*2=4，然后求4的平方，即2的4次方等于4*4=16。到此为止，剩下的4次方也都计算完毕，用当前的16乘以之前的结果256即是最终结果。

本题解题思路实际上与之前分享过的 LEETCODE 29. Divide Two Integers 解题思路分析 这道题目非常类似，我们应该学会融会贯通，举一反三。

实现代码：

public double myPow(double x, int n) {
    // 如果n是0或者x是1，结果一定是1
    if(n==0 || x==1) return 1d;
    // 如果x大于0或者幂是偶数，结果一定大于0
    int markX = x>=0 || n%2==0 ? 1 : -1;
    // 查看n是否大于0
    int markN = n>=0 ? 1 : -1;
    // 将x取绝对值
    x = Math.abs(x);
    // n取绝对值，此处注意，
    // int最小数的绝对值要大于int最大值，因此转换为long型
    long nl = Math.abs((long)n);
    // 返回结果
    double res=1;
    // 当幂大于0
    while(nl>0){
        // 当前已计算的幂
        long count = 1;
        // 当前计算结果
        double d = x;
        // 如果当前计算过的幂的2倍小于nl
        while(count*2<=nl){
            // 当前计算结果进行平方计算
            d*=d;
            // 已计算的幂乘二
            count*=2;
        }
        // 返回结果乘以已计算过幂的结果
        res*=d;
        // 更新剩余还没计算的幂
        nl-=count;
    }
    // 返回结果加上正负号
    res *=markX;
    // 如果幂是负数，用1除以返回结果
    if(markN==-1) res = 1/res;
    return res;
}

本题解法执行时间为1ms

Runtime: 1 ms, faster than 92.40% of Java online submissions for Pow(x, n).

Memory Usage: 39 MB, less than 5.88% of Java online submissions for Pow(x, n).