当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.050.Pow(x,n) 实现Pow(x,n)

LeetCode.050.Pow(x,n) 实现Pow(x,n)

题目描述

50 Pow(x, n)
https://leetcode-cn.com/problems/powx-n/

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:
-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]


相似题目

LeetCode.069.Sqrt(x) x的平方根
LeetCode.050.Pow(x,n) 实现Pow(x,n)


解题过程

快速幂-折半递归

n 是奇数时,$ x^n = (x^{\lfloor n/2 \rfloor})^2 * x $
n 是偶数时,$ x^n = (x^{ n/2 })^2 $
所以,我们每次可以将问题折半,是一种二分法,也是分治的思想

时间复杂度 O(logn),空间复杂度 O(1)

需要注意的地方:
1、每次求 pow(x, n/2),只需要求一次,如果写作 pow(x, n/2) * pow(x, n/2),多了一次无意义的递归,会使计算量直接翻倍,导致超时。
2、测试用例中有 Integer.MIN_VALUE-2147483648,所以必须用 long 型处理 -n ,否则 -n 超过 整型 表示范围会溢出为错误值。

private static class SolutionV2020 {
    public double myPow(double x, int n) {
        // 用 long 型处理 n,避免 -n 溢出
        long nLong = n;
        if (nLong == 0) {
            return 1;
        } else if (nLong < 0) {
            return 1 / pow(x, -nLong);
        } else {
            return pow(x, nLong);
        }
    }

    // 计算 x 的 n 次方, n 是正整数
    private double pow(double x, long n) {
        if (n == 1) {
            return x;
        }
        // 注意避免计算两遍 pow(x, n / 2);
        double temp = pow(x, n / 2);
        if (n % 2 == 0) {
            return temp * temp;
        } else {
            return temp * temp * x;
        }
    }
}

快速幂-二进制分解

把正整数 n 表示为 2 的幂求和的形式
$$ n = 2^{i_0} + 2^{i_1} + … + 2^{i_k} $$
则有
$$
\begin{split}
x^n &= x^{2^{i_0} + 2^{i_1} + … + 2^{i_k}} \\
&= x^{2^{i_0}} * x^{2^{i_1}} * … * x^{2^{i_k}} \\
\end{split}
$$

所以,我们只需计算 x 在 n 二进制分解后各个 1 对应位置上的 2^i 次幂之后相乘即可。


GitHub代码

algorithms/leetcode/leetcode/_050_Pow.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_050_Pow.java


上一篇 LeetCode.560.Subarray Sum Equals K 和为K的子数组

下一篇 LeetCode.069.Sqrt(x) x的平方根

阅读
评论
487
阅读预计2分钟
创建日期 2020-05-11
修改日期 2020-05-11
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论