題目出處
難度
medium
個人範例程式碼
class Solution:
def myPow(self, x: float, n: int) -> float:
# write your code here
# 2 = 1 + 0
# 7 = 1 + 1 + 1
# 5 = 1 + 1 + 0
# 13 = 1 + 1 + 0 + 1
ans = 1
minus_flag = False
if n == 0:
return 1
if n < 0:
minus_flag = True
n = -n
while(n > 0):
if n % 2 == 0:
pass # print(0)
else:
# print(1)
ans *= x
x = x * x
n = n >> 1 # // 2
else:
if minus_flag:
return 1/ans
else:
return ans
算法說明
核心概念為，將 n 次方拆成二進位的方式計算 (這樣就不用重複算)
例如 9 = 8 + 0 + 0 + 1，
我們只重複計算 1^2^2^2^2…. 可以減少一半的計算次數，複雜度為 O(n) -> O(logN)
另外處理負數要特別注意。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理輸入 n = 0 ，return 1,
與輸入 n < 0 ，作負數處理。
Boundary conditions
循環直到當 n 0 時 ( 1//2 = 0 )