LeetCode 题解工作台
Pow(x, n)
实现 pow( x , n ) ，即计算 x 的整数 n 次幂函数（即， x n ）。 示例 1： 输入： x = 2.00000, n = 10 输出： 1024.00000 示例 2： 输入： x = 2.10000, n = 3 输出： 9.26100 示例 3： 输入： x = 2.0000…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数学·递归
答案摘要
快速幂算法的核心思想是将幂指数 拆分为若干个二进制位上的 的和，然后将 的 次幂转化为 的若干个幂的乘积。 时间复杂度 $O(\log n)$，空间复杂度 。其中 为幂指数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·递归 题型思路
题目描述
实现 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
解题思路
方法一：数学（快速幂）
快速幂算法的核心思想是将幂指数 拆分为若干个二进制位上的 的和，然后将 的 次幂转化为 的若干个幂的乘积。
时间复杂度 ，空间复杂度 。其中 为幂指数。
class Solution:
def myPow(self, x: float, n: int) -> float:
def qpow(a: float, n: int) -> float:
ans = 1
while n:
if n & 1:
ans *= a
a *= a
n >>= 1
return ans
return qpow(x, n) if n >= 0 else 1 / qpow(x, -n)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) due to halving the exponent at each recursive call. Space complexity is O(log n) from recursion stack usage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Recognizes negative exponent handling is required.
- question_mark
Uses recursion to optimize repeated multiplications.
- question_mark
Considers integer overflow and floating-point precision issues.
常见陷阱
外企场景- error
Failing to handle n = INT_MIN correctly when negating.
- error
Recomputing pow(x, n//2) multiple times instead of storing intermediate results.
- error
Ignoring base cases for n = 0 or n = 1, causing unnecessary recursion.
进阶变体
外企场景- arrow_right_alt
Implement iterative version to reduce recursion stack usage.
- arrow_right_alt
Extend to handle fractional exponents with floating-point math.
- arrow_right_alt
Support modular exponentiation for large integer powers under modulo constraints.