[算法] 剑指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
}

测试