NO IMAGE

本人一直在努力地積累Leetcode上用Python, C 實現的題,並且會盡力講清每道題的原理,絕不像其他某些部落格簡略地帶過。
如果覺得講的清楚,歡迎關注。

題目:

給定兩個二進位制字串,返回他們的和(用二進位制表示)。

輸入為非空字串且只包含數字 1 和 0

示例 1:

輸入: a = "11", b = "1"
輸出: "100"

示例 2:

輸入: a = "1010", b = "1011"
輸出: "10101"

 

演算法過程:如果想鍛鍊自己不用Python 的包,主要有2種思路:

1.把a和b轉成十進位制後再相加再轉成二進位制

2.直接模擬2進位制加法

 

這裡直接貼出上述2種方法的程式碼:

1.

class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
num1=num2=0
z=0
#轉10進位制
while(1):
if len(a) == 0:
break
num1=num1 pow(2,z)*int(a[-1])
a=a[:-1]
z =1
z = 0
#轉10進位制
while (1):
if len(b) == 0:
break
num2 = num2   pow(2, z) * int(b[-1])
b = b[:-1]
z  = 1
#加十進位制
sum = num1 num2
#轉2進位制,當然也可以自己寫
sum = str(bin(sum)[2:])
return sum

 

2.(完全沒有用其他的包,只不過寫的比較繁瑣,因為寫這道題的時候還很菜。。。)

class Solution:
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
i = 0
res = ""
step = 0
#確定誰比較大(誰長度比較長)
large = max(a, b ,key=len)
small = min(a, b, key=len)
#如果2者相同,隨機分配
if large == small:
large = a
small = b
#從末尾開始模擬
i = len(large) - 1
j = len(small) - 1
while i >= 0  and j >= 0:
#計算
ans = int(large[i])   int(small[j])   step #step用來記錄有沒有進位
if ans > 1:
res = str(ans-2)   res
step = 1
else:
step = 0
res = str(ans)   res
i -= 1
j -= 1
#可能短的走完了長的還沒走完
while i >= 0:
#如果step為0了,則簡單了,直接把剩餘部分搬過來
if step == 0:
res = large[:i 1]   res
break
#若step不為0,則繼續模擬
else:
ans = int(large[i])   step
if ans > 1:
res = str(ans-2)   res
step = 1
i -= 1
else:
res = large[:i]   str(ans)   res
step = 0
break
#如果step還為1,證明這個進位一直傳遞到最高位了
if step == 1:
res = "1"   res
return res

 

當然想簡單,只需一行程式碼:

class Solution:
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
return bin(int(a,2) int(b,2))[2:]

bin是用來把十進位制轉2進位制的,取切片是因為前2位是表示二進位制的一些字元。

int(a,2)的2的意思是告訴這個int函式,你要int的東西是個二進位制而不是十進位制。

 

C

總體思路與方法2python類似,只不過這裡用了一些技巧來簡化程式碼,並且採用的是順序加和,所以需要再結尾處反轉結果。

class Solution {
public:
string addBinary(string a, string b) {
string ret;
int la = a.length();
int lb = b.length();
int lmax = max(la, lb);
int add = '0';
for (int i = 0; i < lmax; i  ) {
//超出的部分就用'0'來代替
char ca = la > i ? a[la-i-1] : '0';
char cb = lb > i ? b[lb-i-1] : '0';
char s = (ca == cb ? '0' : '1');
char sj = (s == add ? '0' : '1');
if (ca == '1' && cb == '1'
|| s == '1' && add == '1') {
add = '1';        
} else {
add = '0';
}
ret  = sj;
}
if (add == '1') {
ret  = add;
}
reverse(ret.begin(), ret.end());
return ret;
}
};