50. Pow(x, n)
50. Pow(x, n)
题目
Implement pow(x, n), which calculates x
raised to the power n
(i.e., xn
).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Constraints:
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
n
is an integer.- Either
x
is not zero orn > 0
. -10^4 <= xn <= 10^4
题目大意
实现 pow(x, n) ,即计算 x 的 n 次幂函数。
解题思路
直接循环相乘可能会超时,因为做了很多重复计算,可以使用二分法来避免重复计算。
- 用递归的方式,不断的将
n
二分下去,每次计算myPow(x, Math.floor(n / 2))
; - 注意
n
为负数时,要提前处理x
; - 注意
n
为奇数时,要手动多乘上一个被省略的x
;
复杂度分析
- 时间复杂度:
O(log n)
- 空间复杂度:
O(1)
代码
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function (x, n) {
if (n == 0) return 1;
if (n == 1) return x;
if (n < 0) {
x = 1 / x;
n = -n;
}
let temp = myPow(x, Math.floor(n / 2));
if (n % 2 == 1) {
return temp * temp * x;
} else {
return temp * temp;
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
69 | x 的平方根 | [✓] | 数学 二分查找 | |
372 | 超级次方 | 数学 分治 | ||
2550 | 猴子碰撞的方法数 | 递归 数学 |