【LeetCode】50. Pow(x, n)

1 问题

实现 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/22 = 1/4 = 0.25

2 答案

自己写的超出时间限制

class Solution:def myPow(self, x: float, n: int) -> float:if n == 0:return 1res = 1for _ in range(abs(n)):res *= xreturn res if n > 0 else 1/res

官方解，利用二进制转十进制

class Solution:def myPow(self, x: float, n: int) -> float:if x == 0.0: return 0.0res = 1if n < 0:x, n = 1/x, -nwhile n:if n & 1:  # 按位与，即 n % 2 == 1res *= xx *= x  n >>= 1  # 即 n % 2 == 1return res 

对于任何十进制正整数 $n$，设其二进制为 $b^m...b^3{b}^2{b}^1$（$b^i$为二进制某位值，$i\in [1,m]$），则有：

• 二进制转十进制：$n=1b_1+2b_2+4b_3+\dots +2^{m-1}{b}_m$ （即二进制转十进制公式）
• 幂的二进制展开：$x^n=x^{1b_1+2b_2+4b_3+\dots +2^{m-1}{b}_m}=x^{1b_1}{x}^{2b_2}{x}^{4b_3}\dots x^{2^{m-1}{b}_m}$