實現 pow(x, n) ，即計算 x 的 n 次冪函數。
示例 1:
輸入: 2.00000, 10輸出: 1024.00000示例 2:
輸入: 2.10000, 3輸出: 9.26100示例 3:
輸入: 2.00000, -2輸出: 0.25000解釋: 2-2 = 1/22 = 1/4 = 0.25說明:
-100.0 < x < 100.0n 是 32 位有符號整數，其數值範圍是 [−2^31, 2^31 − 1] 。來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/powx-n/
Link：https://leetcode.com/problems/powx-n/
暴力破解O(N)
for循環一個個乘
class Solution: def myPow(self, x: float, n: int) -> float:
if x == 0: return 0
if n < 0: n = -n x = 1 / x
res = 1 for i in range(n): res *= x return res二分法O(logN)
分治法以2^10為例:
2^10 = 2^5 * 2^5
2^5 = 2^2 * 2^2 * 2
2^2 = 2 * 2代碼如下:
class Solution: def myPow(self, x: float, n: int) -> float:
if x == 0: return 0
if n < 0: n = -n x = 1 / x
return self.helper(x, n)
def helper(self, x: float, n: int) -> float:
if n == 0: return 1.0
half = self.helper(x, n // 2) if n & 1 == 1: return half * half * x else: return half * half二進位以2^10為例:
# 10的二進位是0b1010
1 0 1 0 # 10的二進位表示4th 3rd 2nd 1st # 遞歸方向⬅️, 每次去掉末尾的一位
2^8 2^4 2^2 2^1 # tmp在參與計算時的值把二進位奇數部分相加2^8 + 2^2 = 2^10代碼如下:
class Solution: def myPow(self, x: float, n: int) -> float:
if x == 0: return 0
if n < 0: n = -n x = 1 / x
res = 1 tmp = x
while n > 0: if n & 1 == 1: res = res * tmp
tmp = tmp * tmp n = n // 2
return res倍增思想以2^10為例, 倍增的思想瘋狂試探
# 第一次試探2^1, 2^2, 2^4, 2^8, 2^16, 最後一個超了, 算到了2^8次方
# 第二次試探2^1, 2^2, 2^4, 最後一個超了，剛好算到2^2次方代碼如下
class Solution: def myPow(self, x: float, n: int) -> float:
if x == 0: return 0
exp = abs(n) res = 1
while exp > 0: mark = 1 tmp = x while (mark << 1) < exp: tmp = tmp * tmp mark = (mark << 1)
exp -= mark res *= tmp return res if (n > 0) else 1 / res--End--