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：先計算指數(shù)的二進制, 再累乘每個二進制位的乘方值
- 首先, 如果按照固定循環(huán)來乘, 肯定復(fù)雜度太高, 直觀上可以想到二進制
-
可以利用乘方性質(zhì), 對指數(shù)進行二進制變換, 例如
image.png
而又有
image.png
可以利用這個性質(zhì),
- 先計算13對應(yīng)的二進制, 由低位到高位依次為[1, 0, 1, 1]
- 再依次計算每個二進制位對應(yīng)的x的乘方值, 然后視該二進制位是否為1, 來決定是否將此乘方值乘到結(jié)果值上
- 如果指數(shù)是負數(shù), 則將上一步計算的結(jié)果取倒數(shù)
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))
輸出結(jié)果
1024.0
9.261000000000001
0.25
4. 結(jié)果
image.png
