【LeetCode】50. Pow(x, n)
1 问题
实现 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/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 n n，设其二进制为 b m . . . b 3 b 2 b 1 b^m...b^3b^2b^1 bm...b3b2b1（ b i b^i bi为二进制某位值， i ∈ [ 1 , m ] i \in [1,m] i∈[1,m]），则有：
- 二进制转十进制： n = 1 b 1 + 2 b 2 + 4 b 3 + … + 2 m − 1 b m n=1 b_1+2 b_2+4 b_3+\ldots+2^{m-1} b_m n=1b1+2b2+4b3+…+2m−1bm （即二进制转十进制公式）
- 幂的二进制展开： x n = x 1 b 1 + 2 b 2 + 4 b 3 + … + 2 m − 1 b m = x 1 b 1 x 2 b 2 x 4 b 3 … x 2 m − 1 b m x^n=x^{1 b_1+2 b_2+4 b_3+\ldots+2^{m-1} b_m}=x^{1 b_1} x^{2 b_2} x^{4 b_3} \ldots x^{2^{m-1} b_m} xn=x1b1+2b2+4b3+…+2m−1bm=x1b1x2b2x4b3…x2m−1bm