67. 二进制求和

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

碰到这个题目的第一个思路，转换为十进制求和，刚刚好熟悉一下 golang strconv 库

func addBinary(a string, b string) string {
    ai, err := strconv.ParseInt(a, 2, 64)
    if err != nil {
        fmt.Println(ai, err)
    }
    bi, err := strconv.ParseInt(b, 2, 64)
    return fmt.Sprintf("%b", ai+bi)
}

不出意外，提交不通过，不通过的测试为

c := "10100000100100110110010000010101111011011001101110111111111101000000101111001110001111100001101"
d := "110101001011101110001111100110001010100001101011101010000011011011001011101111001100000011011110011"

这个测试的想法当然是让我们自己算了，ok，没有问题，计算二进制加法很简单，定义一个二进制加法函数（记得考虑进位）

func binadd(x, y, flag int) (sum, addflag int) {
    sum = (x + y + flag) % 2
    addflag = (x + y + flag) / 2
    return
}

好吧，为了配合输入输出是字符串，还需要转换一下

func binStr2Slice(BinStr string) []int {
    temp := make([]int, len(BinStr), len(BinStr))
    for i := 0; i < len(BinStr); i++ {
        if BinStr[i] == '0' {
            temp[i] = 0
        } else {
            temp[i] = 1
        }
    }
    return temp
}

func binSlice2str(b []int) string {
    s := ""
    for _, v := range b {
        s = s + fmt.Sprint(v)
    }
    return s
}

addBinary 需要一个遍历的过程

func addBinaryS(a string, b string) string {
    if len(a) < len(b) {
        a, b = b, a
    }
    maxL := len(a)
    aint := binStr2Slice(a)
    bint := binStr2Slice(b)

    addFlag := 0
    sum := make([]int, maxL, maxL)
    for i := 1; i <= maxL; i++ {
        if i <= len(b) {
            sum[len(sum)-i], addFlag = binadd(aint[len(aint)-i], bint[len(bint)-i], addFlag)
        } else {
            sum[len(sum)-i], addFlag = binadd(aint[len(aint)-i], 0, addFlag)
        }

    }
    if addFlag == 1 {
        sum = append([]int{1}, sum...)
    }
    return binSlice2str(sum)
}

PASS

附上0ms通过的代码，里面使用了字符加减的设计，个人感觉不是很好理解，所以不做分析

func addBinary(a string, b string) string {
    var carry, sum int
    i, j := len(a), len(b)
    if i < j {
        i, j = j, i
        a, b = b, a
    }

    res := make([]byte, i+1)

    for j > 0 {
        j--
        i--
        sum = int(a[i]-'0') + int(b[j]-'0') + carry
        carry = sum / 2
        sum = sum % 2
        res[i+1] = byte(sum + '0')
    }

    for i > 0 {
        i--
        sum = int(a[i]-'0') + carry
        carry = sum / 2
        sum = sum % 2
        res[i+1] = byte(sum + '0')
    }

    res[0] = byte(carry + '0')

    for i < len(res)-1 {
        if res[i] == '0' {
            i++
        } else {
            break
        }
    }
    return string(res[i:])
}