題目出處
難度
medium
個人範例程式碼
class Solution:
"""
@param a: A 32bit integer
@param b: A 32bit integer
@param n: A 32bit integer
@return: An integer
"""
def fast_power(self, a: int, b: int, n: int) -> int:
ans, tmp = 1, a
while(n > 0):
if(n % 2 == 1):
ans = (ans * tmp) % b
tmp = (tmp * tmp) % b
n = n // 2
else:
return ans % b
算法說明
- 有非常類似的問題，詳細說明可參考：【Leetcode】python – [50] Pow(x, n) 個人解法筆記
核心概念為，將 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 )