未分類

Add Binary

Go, LeetCode, Math, String

Add Binary

Given two binary strings, return their sum (also a binary string).

For Example:

1
2
3
a = "11"
b = "1"
Return "100".
提示 解題應用
String 觀查規律
Math 觀查規律

Default:

1
2
3
func addBinary(a string, b string) string {
}

解答思路:

一般來說看到題目就會曉得1與1就進位，0與1則為1，0與0則為0，這三個基本上就是二進位加法的全部了，不過因為有可能長度會不一樣，也許將短的前頭捕一排0也是個辦法，不過一開始嫌麻煩就直接將兩個先轉成數字加起來，位數合為2的就進位，看起來就簡單非常多，寫好送出馬上就發現了大問題，就是給的參數數字未免也太龐大的，連int64都放不下，可想而之就是要你乖乖的用字串來處理，而這邊我將較長的部分給拆開變成兩個參數一樣長，待判斷完如果有進位再與原本較長的部分判斷，好處就是如果沒有進位，原本較長拆開多出的二進字串最後就直接接在前面就搞定了，尤其是兩個參數差異極大步驟就少了許多。

程式碼解說:

因為相加一定是從尾數開始，所以拿到兩個字串長度後，用一個迴圈來將兩個字串分別從尾部將字元一一取出，之後正如一開始所說的1與1就是回傳1，其中一個為1的就是回傳1，而兩個為0則為0，不過因為還要考量到進位的問題，用了一個flag在確認是否有進位，所以上述的情況就又各別多了進位後會產生的回傳，好比兩個皆為1時，但如果又有進位值來該位數+1的話，這時的位數就不是0而是為1了，其它的就以此類推，要注意的是在迴圈一開始的判斷式是用來得知哪一個參數字串的長度比較長，而比較短的在從最後頭取值時自然就會先歸0了，這時就將另一個較長多餘的部分連同長度給另存起來到下一個迴圈繼續處理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
var tmp string
var length int
var result string
var achar string
var bchar string
alen := len(a)
blen := len(b)
flag := false
for true {
	if alen == 0 {
		tmp = b[0:blen]
		length = blen
		break
	}else if blen == 0 {
		tmp = a[0:alen]
		length = alen
		break
	}
	achar = string(a[alen-1])
	bchar = string(b[blen-1])
	if achar == "1" && bchar == "1" {
		if flag {
			result = "1" + result
			flag = true
		} else {
			result = "0" + result
			flag = true
		}
	} else if achar == "1" || bchar == "1" {
		if flag {
			result = "0" + result
			flag = true
		} else {
			result = "1" + result
			flag = false
		}
	} else {
		if flag {
			result = "1" + result
			flag = false
		} else {
			result = "0" + result
			flag = false
		}
	}
	alen--
	blen--
}

接續先前相同長度時的比較，接下來的迴圈就是先前的結果是否進位與多餘長度字串的處理，這次我們只要知道這個拆出去字串的字元是0還是1，接下來只要視之前結果有無進位來判斷即可，不過如果沒有進位的話就不需要再讓迴圈執行下去了，將拆出去而暫存字串依目前剩餘的長度，直接與先前結果相接即可，因為要比較的只有進位與剩下的字串，如果沒有進位理所當然就不同繼續，但如果是進位到底而超出了原本字串的長度時，好比99+1為100時，那麼最後就在開頭補上1結束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
for true {
	if length == 0 {
		if flag {
			result = "1" + result
		}
		break
	}
	tchar = string(tmp[length-1])
	if tchar == "1" {
		if flag {
			result = "0" + result
			flag = true
		} else {
			result = tmp[0:length] + result
			break
		}
	} else {
		if flag {
			result = "1" + result
			flag = false
		} else {
			result = tmp[0:length] + result
			break
		}
	}
	length--
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
func addBinary(a string, b string) string {
	var tmp string
	var length int
	var result string
	var achar string
	var bchar string
	var tchar string
	alen := len(a)
	blen := len(b)
	flag := false
	for true {
		if alen == 0 {
			tmp = b[0:blen]
			length = blen
			break
		}else if blen == 0 {
			tmp = a[0:alen]
			length = alen
			break
		}
		achar = string(a[alen-1])
		bchar = string(b[blen-1])
		if achar == "1" && bchar == "1" {
			if flag {
				result = "1" + result
				flag = true
			} else {
				result = "0" + result
				flag = true
			}
		} else if achar == "1" || bchar == "1" {
			if flag {
				result = "0" + result
				flag = true
			} else {
				result = "1" + result
				flag = false
			}
		} else {
			if flag {
				result = "1" + result
				flag = false
			} else {
				result = "0" + result
				flag = false
			}
		}
		alen--
		blen--
	}
	for true {
		if length == 0 {
			if flag {
				result = "1" + result
			}
			break
		}
		tchar = string(tmp[length-1])
		if tchar == "1" {
			if flag {
				result = "0" + result
				flag = true
			} else {
				result = tmp[0:length] + result
				break
			}
		} else {
			if flag {
				result = "1" + result
				flag = false
			} else {
				result = tmp[0:length] + result
				break
			}
		}
		length--
	}
	return result
}

總結:

二進位的相加不能轉成數字相加再處理，因為有可能給的參數過大而導致溢位，所以一定要以字串來判斷處理，當遇上長度不一的二進位做相加時，可以以補0或是將較長多餘的部分拆開做第二次處理，若為後者再最後處理時僅為進位與多餘部分字串的判斷。

分享到