Try   HackMD

Leetcode 67 add binary string

  1. 二進位加法
  2. % 用來取餘數
  3. // 用來取整數作為進位

My Solution 時間複雜 O(max(len(a), len(b)))

def addBinary(self, a, b): # 輸入二進位兩個數字,要你做加法 # a,b % 10 餘數為10 or 1 # 如果不是餘10 or 1 回傳空值 if not (a%10 == 0 or a%10 == 1) / and (b % 10 == 0 or b % 10 == 1): return "" # 如果兩個都為0 if int(a)==0 and int(b)==0: return "0" # str(a) 會是反過來 list_a = [i for i in a] # 剛開始讀取 list_b = [j for j in b] list_a.reverse() # python內建陣列反轉 # list_a = [list_a[i] for i in range(len(list_a)-1,-1,-1)] #反過來 list_b = [list_b[i] for i in range(len(list_b)-1,-1,-1)] #反過來 a_num = 0 ; b_num=0 # 將反轉後的陣列利用enumerate換成10進位 for index,num in enumerate(list_a): a_num += 2**(index)*int(num) for index,num in enumerate(list_b): b_num += 2**(index)*int(num) sum = a_num+b_num ; x = 0 # 尋找最接近的次方 while (2**x <= sum): x+=1 x-=1 ; ans ="" # 從最大次方開始作,%取餘數 //取整數 for i in range(x,-1,-1): ans += str(sum // (2**i)) sum %= (2**i) return ans

Best Solution 我也有想出來更好的算法 DP解
時間 O(max(len(a), len(b)))

def addBinary(self, a, b): list_a = [i for i in str(a)] list_b = [i for i in str(b)] i = len(list_a)-1; j= len(list_b)-1; plus = 0 ; ans = '' while i>=0 or j>=0 or plus==1: if i>=0: # 從最右邊開始作相加 plus+=int(list_a[i]) if j>=0: # 從最右邊開始作相加 plus+=int(list_b[j]) # 前面位數為大的,取餘數作輸出 # ex:3%2=1,因此要填入1,新加入字串在左邊 ans = str(plus % 2) +ans # plus 3//2=1 代表要進位,把plus帶到下一個位數 # 通常 plus 只會有 3//2 or 2//2 i, j, plus = i-1, j-1, plus//2 return ans
tags: LeetCode binary add