image.png
0. 链接
1. 题目
Implement pow(x, n), which calculates x raised to the power n (xn).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
- -100.0 < x < 100.0
- n is a 32-bit signed integer, within the range [−231, 231 − 1]
2. 思路1：先计算指数的二进制, 再累乘每个二进制位的乘方值
- 首先, 如果按照固定循环来乘, 肯定复杂度太高, 直观上可以想到二进制
-
可以利用乘方性质, 对指数进行二进制变换, 例如
image.png
而又有
image.png
可以利用这个性质,
- 先计算13对应的二进制, 由低位到高位依次为[1, 0, 1, 1]
- 再依次计算每个二进制位对应的x的乘方值, 然后视该二进制位是否为1, 来决定是否将此乘方值乘到结果值上
- 如果指数是负数, 则将上一步计算的结果取倒数
3. 代码
# coding:utf8
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0:
return 0
sign = 1 if n == abs(n) else -1
n = abs(n)
rtn = 1
value = x
while n > 0:
if n % 2 > 0:
rtn *= value
value *= value
n >>= 1
return rtn if sign == 1 else 1.0 / rtn
solution = Solution()
print(solution.myPow(2.00000, 10))
print(solution.myPow(2.10000, 3))
print(solution.myPow(2.00000, -2))
输出结果
1024.0
9.261000000000001
0.25
4. 结果
image.png
