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.371.Sum of Two Integers 不用加减号计算整数加法
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