Pow(x, n)
难度:
标签:
题目描述
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-231 <= n <= 231-1n是一个整数- 要么
x不为零，要么n > 0。 -104 <= xn <= 104
代码结果
运行时间: 36 ms, 内存: 14.8 MB
/*
* 题目思路：
* 使用 Java Stream 实现 pow(x, n) 函数。
* 由于 Stream 不能直接用于指数运算，我们可以使用递归方式或者自定义操作来实现。
* 这里使用传统方法来完成题目要求，因为 Stream 的优势在于并行计算和集合操作。
*/
public class Solution {
public double myPow(double x, int n) {
if (n == 0) return 1;
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return powHelper(x, N);
}
private double powHelper(double x, long n) {
if (n == 0) return 1;
double half = powHelper(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
}解释
方法:
该题解使用快速幂算法，通过二分法将幂次 n 分解，每次将 n 除以2，同时将底数 x 平方，直到 n 为0。若 n 为奇数，则将当前答案乘以底数 x。最终得到 x 的 n 次幂结果。若 n 为负数，则先将 x 取倒数，同时将 n 取相反数，转化为正数的情况。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在快速幂算法中，为什么选择每次对n进行二进制右移操作？这样的操作有什么特别的好处吗？
▷🦆
在处理n为负数的情况时，为什么要将x取倒数并将n取相反数？这种操作对算法的结果有何影响？
▷🦆
快速幂算法中，如果n的二进制表示中有多个1，例如n = 11（二进制为1011），算法是如何确保正确计算x的n次幂的？
▷🦆
在代码中使用`if n & 1 != 0`来检查n的最低位是否为1，这种方法与直接检查n是否为奇数有什么不同？
▷