[算法] 劍指offer2 golang 面試題2：二進制加法

題目1:

給定兩個 01 字符串 a 和 b ，請計算它們的和，並以二進制字符串的形式輸出。

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

示例 1:

輸入: a = “11”, b = “10”
輸出: “101”
示例 2:

輸入: a = “1010”, b = “1011”
輸出: “10101”

提示：

每個字符串僅由字符 ‘0’ 或 ‘1’ 組成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前導零。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/JFETK5
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路1: 模擬二進制加法

模擬二進制加法時間複雜度 O(n)

代碼

func addBinary(a string, b string) string {
    
	//思路: 模擬二進制計算
	length := len(a)
	if len(b) > len(a) {
    
		length = len(b)
	}
	//構造返回
	resBs := make([]byte, length)
	//從後往前指向的指針
	aP, bP := len(a)-1, len(b)-1
	//是否進比特
	up := 0
	for i := len(resBs) - 1; i >= 0; i-- {
    
		var aByte byte = '0'
		var bByte byte = '0'
		if aP >= 0 {
    
			aByte = a[aP]
			aP--
		}
		if bP >= 0 {
    
			bByte = b[bP]
			bP--
		}
		// 統計個數
		count1 := 0
		if aByte == '1' {
    
			count1++
		}
		if bByte == '1' {
    
			count1++
		}
		count1 += up
		//通過個數確定當前值和up
		if count1 == 0 {
    
			up = 0
			resBs[i] = '0'
		} else if count1 == 1 {
    
			up = 0
			resBs[i] = '1'
		} else if count1 == 2 {
    
			up = 1
			resBs[i] = '0'
		} else {
    
			up = 1
			resBs[i] = '1'
		}
	}
	//最後的up
	res := string(resBs)
	if up == 1 {
    
		res = "1" + res
	}
	return res
}

測試