LeetCode 50. Pow(x, n) 题解

LeetCode 50. 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.00000, n -2 输出0.25000 解释2^-2 1/2^2 1/4 0.25解题思路快速幂算法利用分治法将指数 n 分解为二进制形式例如x^10 x^8 * x^2时间复杂度 O(log n)代码实现def myPow(x, n): if n 0: return 1.0 # 处理负数指数 if n 0: x 1 / x n -n result 1.0 while n 0: # 如果当前位是 1乘到结果中 if n % 2 1: result * x # 平方底数 x * x # 右移一位 n // 2 return result复杂度分析时间复杂度O(log n)空间复杂度O(1)递归实现def myPow(x, n): if n 0: return 1.0 if n 0: return 1.0 / myPow(x, -n) half myPow(x, n // 2) if n % 2 0: return half * half else: return half * half * x测试案例# 测试案例 1 assert abs(myPow(2.0, 10) - 1024.0) 1e-5 # 测试案例 2 assert abs(myPow(2.1, 3) - 9.261) 1e-5 # 测试案例 3 assert abs(myPow(2.0, -2) - 0.25) 1e-5 # 测试案例 4 assert abs(myPow(0.0, 1) - 0.0) 1e-5 # 测试案例 5 assert abs(myPow(1.0, 1000000) - 1.0) 1e-5总结本题是快速幂算法的经典应用。关键点快速幂的迭代实现处理负数指数边界条件处理通过本题可以深入理解分治法的应用。