pow
- 题目
- 题目描述
- 示例 1:
- 示例 2:
- 示例 3:
- 提示:
- 题解
- 解题思路
- python
- 代码解释
- 提交结果
题目
题目描述
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即, 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 / 2 2 = 1 / 4 = 0.25 2^{-2} = 1/2^2 = 1/4 = 0.25 2−2=1/22=1/4=0.25
提示:
-100.0 < x < 100.0
− 2 31 < = n < = 2 31 − 1 -2^{31} <= n <= 2^{31}-1 −231<=n<=231−1
n 是一个整数
要么 x 不为零,要么 n > 0 。
− 1 0 4 < = x n < = 1 0 4 -10^4 <= x^n <= 10^4 −104<=xn<=104
题解
要实现pow(x, n)
函数,即计算 x n x^n xn,可以使用快速幂算法。这个算法的核心思想是通过将指数不断减半来减少乘法运算的次数,从而大大提高了效率。快速幂算法适用于整数和浮点数,并且可以处理正指数和负指数的情况。
解题思路
- 处理特殊情况:如果 n = 0 n=0 n=0,那么任何数的0次幂都是1(除了0^0,在数学上有时认为是未定义的,但在此题目中我们可以返回1)。
- 处理负指数:如果 n < 0 n<0 n<0,则可以通过计算 x − n x^{-n} x−n然后取其倒数得到结果。这是因为 x − n = 1 / x n x^{-n} = 1/x^n x−n=1/xn。
- 快速幂算法:对于正整数 n n n,使用迭代或递归的方法,将 n n n减半的同时平方底数 x x x。如果 n n n为奇数,则还需要额外乘一次 x x x。
python_36">python
下面是Python代码实现:
python">def myPow(x: float, n: int) -> float:# 处理负指数if n < 0:x = 1 / xn = -nresult = 1while n:# 如果n是奇数,就乘以当前的xif n % 2:result *= x# 将x平方,准备下一轮的计算x *= x# n除以2,向下取整n //= 2return result
代码解释
这段代码实现了快速幂算法,它能够有效地计算 x n x^n xn,其中 n n n可以是任意整数(包括负数)。该算法的时间复杂度为O(log n),因为每次循环 n n n都会被减半;空间复杂度为O(1),因为我们只用了常数级别的额外空间来存储结果和其他变量。
此方法能很好地满足题目给出的所有条件和限制,包括处理大范围内的 n n n值以及确保输出在规定的范围内。