class Solution {
public:
double myPow(double x, int n) {
}
};
剑指 Offer 16. 数值的整数次方
实现 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-1-104 <= xn <= 104
注意：本题与主站 50 题相同：https://leetcode.cn/problems/powx-n/
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2022-11-14 10:03:28
func myPow(x float64, n int) float64 {
var quickMul = func(m int) float64 {
cx := x
ans := 1.0
for m > 0 {
if m % 2 == 1 {
ans *= cx
}
cx *= cx
m /= 2
}
return ans
}
if n >= 0 {
return quickMul(n)
}
return 1.0/quickMul(-n)
}
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-11-14 09:53:22
class Solution:
def myPow(self, x: float, n: int) -> float:
# 快速幂 + 迭代
def quickMul(N: int):
ans = 1.0
# 贡献的初始值为 x
x_contribute = x
# 在对 N 进行二进制拆分的同时计算答案
while N > 0:
if N % 2 == 1:
# 如果 N 二进制表示的最低位为 1，那么需要计入贡献
ans *= x_contribute
# 将贡献不断地平方
x_contribute *= x_contribute
# 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
N //= 2
return ans
return quickMul(n) if n >= 0 else 1.0 / quickMul(-n)